Pagini recente » Monitorul de evaluare | Cod sursa (job #245856) | Cod sursa (job #993984) | Clasament oni-2009-xi-xii | Cod sursa (job #164956)
Cod sursa(job #164956)
#include <stdio.h>
#define act ((x&i)?1:0)
const long MAX = 100010;
const long mx = 30;
long m = -1, st,dr;
long A[MAX];
long n, i;
struct trie {
long info;
trie *f[2];
} *root = new trie;
void trie_add(long x, long y) {
long i;
trie *r = root;
for (i=1<<mx; i; i>>=1) {
if ( !r->f[act] ) {
r->f[act] = new trie;
*(r->f[act]) = (trie){0,{0,0}};
}
r = r->f[act];
}
r->info = y;
}
int trie_search(long x) {
long i; trie *r = root;
for (i=1<<mx; i; i>>=1) {
if ( r->f[!act] ) {
r = r->f[!act];
continue ;
}
if ( r->f[act] ) {
r = r->f[act];
continue ;
}
return -1;
}
return r->info;
}
int main() {
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%ld", &n);
trie_add(0,0);
for (i=1; i<=n; ++i) {
long x;
scanf("%ld", &x);
A[i] = A[i-1] ^ x;
long p = trie_search(A[i]);
if ( p!=-1 ) {
if ( m<(A[i]^A[p]) ) {
st = p+1; dr = i; m = A[i]^A[p];
}
}
trie_add(A[i], i);
}
printf("%ld %ld %ld\n", m, st,dr);
return 0;
}