Pagini recente » Cod sursa (job #2038265) | Cod sursa (job #1498528) | Cod sursa (job #2542956) | Cod sursa (job #3179945) | Cod sursa (job #1808478)
#include <cstdio>
const int SIGMA = 2;
const int BIT_MAX = 20;
class Trie {
public:
int inf;
Trie* son[SIGMA];
Trie() {
inf = 0;
for(int i = 0; i < SIGMA; ++i)
son[i] = NULL;
}
void add(int x, int bit, int poz) {
int extr;
if(bit == -1) {
if(poz > inf)
inf = poz;
} else {
extr = (x & (1 << bit)) > 0;
if(son[extr] == NULL)
son[extr] = new Trie;
son[extr] -> add(x, bit - 1, poz);
}
}
};
int main() {
int n, s, x, extr, best;
int max, st, dr;
Trie *t, *cursor;
t = new Trie;
t -> add(0, BIT_MAX - 1, 0);
FILE *fin = fopen("xormax.in", "r");
fscanf(fin, "%d", &n);
s = 0;
max = st = dr = 0;
for(int i = 1; i <= n; ++i) {
fscanf(fin, "%d", &x);
s = s ^ x;
cursor = t;
best = 0;
for(int i = BIT_MAX - 1; i >= 0; --i) {
extr = (s & (1 << i)) > 0;
if(cursor -> son[1 - extr] != NULL) {
best = (best << 1) | 1;
cursor = cursor -> son[1 - extr];
} else {
best = best << 1;
cursor = cursor -> son[extr];
}
}
if(best > max) {
max = best;
dr = i;
st = cursor -> inf;
} else if(best == max) {
dr = i;
st = cursor -> inf;
}
t -> add(s, BIT_MAX - 1, i);
}
fclose(fin);
FILE *fout = fopen("xormax.out", "w");
fprintf(fout, "%d %d %d", max, st + 1, dr);
fclose(fout);
return 0;
}