Pagini recente » Cod sursa (job #2445476) | Cod sursa (job #2175585) | Cod sursa (job #1184570) | Cod sursa (job #2442685) | Cod sursa (job #81621)
Cod sursa(job #81621)
#include <cstdio>
#define FIN "xormax.in"
#define FOUT "xormax.out"
#define MAX 100001
#define bit(x,i) ((x>>i)&1)
#define __debug__ 0
long A[MAX], P[MAX];
long i,n;
long max;
long st, fi;
class trie {
public:
struct nod {
long *fin;
nod *f[2];
};
private:
nod* root;
long H;
nod* creeaza() {
nod* p = new nod;
p -> f[0] = p->f[1] = 0;
p->fin = 0;
return p;
}
public:
trie(long height) {
H = height;
root = creeaza();
}
void add(long x, long pos) {
long i;
if ( __debug__ )
printf(" Adding(%3ld)... ",x);
nod *p = root;
for (i=H-1; i>=0; --i) {
if ( p->f[ bit(x,i) ] ) {
if ( __debug__ )
printf("%ld", bit(x,i));
p = p->f[ bit(x,i) ];
}
else {
p->f[ bit(x,i) ] = creeaza();
p = p->f[ bit(x,i) ];
if ( __debug__ )
printf("(%ld)", bit(x,i));
}
}
if ( __debug__ )
printf(" --> %ld\n", x);
p -> fin = new long;
*(p->fin) = pos;
};
bool search(long x) {
long i;
nod *p = root;
for (i=H-1; i>=0; --i) {
if ( p->f[ bit(x,i) ] )
p = p->f[ bit(x,i) ];
else
return false;
}
return (p -> fin)!=0;
};
long search_l(long x) {
long i;
nod *p = root;
if ( __debug__ )
printf(" Searching(%3ld)... ",x);
for (i=H-1; i>=0; --i) {
if ( p->f[ !bit(x,i) ] ) {
p = p->f[ !bit(x,i) ];
if ( __debug__ )
printf("%ld",!bit(x,i));
}
else {
p = p->f[ bit(x,i) ];
if ( __debug__ )
printf("(%ld)",bit(x,i));
}
}
if ( __debug__ )
printf(" == %ld\n", *(p->fin));
return *(p->fin);
}
} T(23);
int main() {
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%ld", &n);
for (i=0; i<n; ++i) {
scanf("%ld", A+i);
if ( !i )
P[i] = A[i];
else
P[i] = P[i-1] ^ A[i];
T.add(P[i],i);
long tmp = T.search_l(P[i]);
if ( __debug__ )
printf("Max: %5ld Act:%5ld\n", max, P[i]^P[tmp]);
if ( max<P[i]^P[tmp] ) {
max = P[i]^P[tmp];
st = tmp+1;
fi = i;
}
}
printf("%ld %ld %ld\n", max, st+1, fi+1);
fclose(stdout);fclose(stdin);
return 0;
}