Pagini recente » Cod sursa (job #1904914) | Cod sursa (job #2647079) | Monitorul de evaluare | Cod sursa (job #2022042) | Cod sursa (job #2074785)
#include <cstdio>
const int MAXN = 1e5;
#define lim (1 << 21)
struct trie {
int pos;
trie *son[2];
trie() {
pos = 0;
son[0] = son[1] = 0;
}
};
trie *t = new trie;
int v[2 * MAXN + 1];
void add(trie *node, int p, int x) {
if (!x) {
node->pos = p;
return;
}
if (!(node->son[(v[p] & x) > 0])) {
node->son[(v[p] & x) > 0] = new trie;
}
add(node->son[(v[p] & x) > 0], p, x >> 1);
}
int maxxor(trie *node, int p, int x) {
if (!x) {
return node->pos;
}
if (node->son[!((v[p] & x) > 0)]) {
return maxxor(node->son[!((v[p] & x) > 0)], p, x >> 1);
}
return maxxor(node->son[(v[p] & x) > 0], p, x >> 1);
}
int main() {
int n, st, dr, max, x;
FILE * f = fopen("xormax.in", "r");
fscanf(f, "%d", &n);
add(t, 0, lim);
max = -lim;
for (int i = 1; i <= n; ++i) {
fscanf(f, "%d", &v[i]);
v[i] ^= v[i - 1];
x = maxxor(t, i, lim);
if (max < (v[i] ^ v[x])) {
max = (v[i] ^ v[x]);
dr = i;
st = x + 1;
}
add(t, i, lim);
}
fclose(f);
f = fopen("xormax.out", "w");
fprintf(f, "%d %d %d\n", max, st, dr);
fclose(f);
}