Pagini recente » Istoria paginii runda/simulareblabla | Cod sursa (job #1882969) | Istoria paginii runda/simulareoji2017 | Cod sursa (job #2009078) | Cod sursa (job #1569562)
#include <cstdio>
const int nMaxBit = 20;
int partialXor[100005];
class Trie {
public:
int p;
Trie* fii[2];
Trie() {
fii[0] = fii[1] = NULL;
p = 0;
}
void insert(int n, int b, int v) {
if(b < 0)
p = v;
else {
bool x = n & (1 << b);
if(fii[x] == NULL)
fii[x] = new Trie();
fii[x]->insert(n, b - 1, v);
}
}
int query(int n, int b = nMaxBit) {
if(b < 0)
return p;
bool x = !(n & (1 << b));
if(fii[x] == NULL)
x = !x;
return fii[x]->query(n, b - 1);
}
} *lambda = new Trie();
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
int N, nr, pos[3], sum, Max;
scanf("%d", &N);
lambda->insert(0, nMaxBit, 0);
sum = pos[0] = 0;
Max = pos[1] = pos[2] = -1;
for(int i = 1; i <= N; ++ i) {
scanf("%d", &nr); sum ^= nr;
partialXor[i] = sum;
pos[0] = lambda->query(sum);
if((sum ^ partialXor[pos[0]]) > Max) {
Max = sum ^ partialXor[pos[0]];
pos[1] = pos[0] + 1;
pos[2] = i;
}
lambda->insert(sum, nMaxBit, i);
}
printf("%d %d %d\n", Max, pos[1], pos[2]);
return 0;
}