Pagini recente » Cod sursa (job #2402193) | Cod sursa (job #2622521) | Cod sursa (job #2919293) | Cod sursa (job #2069960) | Cod sursa (job #150336)
Cod sursa(job #150336)
#include <cstdio>
#define act ((x&i)?1:0)
#define __debug__
#ifdef __debug__
const long MAX = 100;
#else
const long MAX = 100010;
#endif
const long mx = 25;
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);
scanf("%ld", &n);
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 ) { // found ok
if ( m<(A[i]^A[p]) ) {
st = p+1; dr = i; m = A[i]^A[p];
}
}
trie_add(A[i], i);
}
if ( n-1 )
fprintf(fopen("xormax.out", "w"), "%ld %ld %ld\n", m, st,dr);
else
fprintf(fopen("xormax.out", "w"), "1 1 %ld\n", A[1]);
return 0;
}