Pagini recente » Cod sursa (job #543024) | Cod sursa (job #1178018) | Cod sursa (job #2826333) | Cod sursa (job #2354441) | Cod sursa (job #1808490)
#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, 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 j = BIT_MAX; j >= 0; --j) {
extr = (s & (1 << j)) > 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;
}
t -> add(s, BIT_MAX, i);
}
fclose(fin);
FILE *fout = fopen("xormax.out", "w");
fprintf(fout, "%d %d %d", max, st + 1, dr);
fclose(fout);
return 0;
}