Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Statistici Cristina (Cristinutaa) | Cod sursa (job #1776779) | Cod sursa (job #2006845)
#include <stdio.h>
class trie{
public:
int inf;
trie *son[2];
trie() {
inf = 0;
for(int i = 0;i < 2;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);
}
}
};
FILE *fin, *fout;
int main() {
fin = fopen("xormax.in", "r");
fout = fopen("xormax.out", "w");
int n, max, st, dr, extr, bst;
trie *t, *cursor;
t = new trie;
t -> add(0, 20, 1);
int s = 0;
max = -1, st = -1, dr = -1;
fscanf(fin, "%d", &n);
for(int i = 1;i <= n;i++) {
int x;
fscanf(fin, "%d", &x);
s = s ^ x;
cursor = t;
bst = 0;
for(int j = 20;j >= 0;j--) {
extr = (s & (1 << j)) > 0;
if(cursor -> son[1 - extr] != NULL) {
bst = (bst << 1) | 1;
cursor = cursor -> son[1 - extr];
}
else {
bst = bst << 1;
cursor = cursor -> son[extr];
}
}
if(max < bst)
max = bst, dr = i, st = cursor -> inf;
t -> add(s, 20, i + 1);
}
fprintf(fout, "%d %d %d", max, st, dr);
fclose(fin);
fclose(fout);
return 0;
}