Pagini recente » Cod sursa (job #2471295) | Cod sursa (job #2053128) | Cod sursa (job #333074) | Cod sursa (job #2891019) | Cod sursa (job #661776)
Cod sursa(job #661776)
#include<stdio.h>
#include<string.h>
#define inf "xormax.in"
#define outf "xormax.out"
#define NMax 100001
#define INF 0x3f3f3f3f
using namespace std;
int N, A[NMax], S[NMax];
const int bits = 20;
void read()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d", &A[i]);
}
struct Trie {
int ind;
Trie* fiu[2];
Trie() {
ind = 0;
memset( fiu, 0, sizeof(fiu) );
}
};
Trie *T = new Trie();
void insert(Trie *nod, int x, int ind) {
for(int i=bits; i>=0; i--) {
int bit = x & (1<<i);
if( bit ) {
if( nod->fiu[1]==0 ) nod->fiu[1] = new Trie();
nod = nod->fiu[1];
continue;
}
if( nod->fiu[0]==0 ) nod->fiu[0] = new Trie();
nod = nod->fiu[0];
}
nod->ind = ind;
}
int que(Trie *nod, int x) {
for(int i=bits; i>=0; i--) {
int bit = x & (1<<i);
if( bit ) {
if( nod->fiu[0] ) nod = nod->fiu[0];
else nod = nod->fiu[1];
}
else {
if( nod->fiu[1] ) nod = nod->fiu[1];
else nod = nod->fiu[0];
}
}
return nod->ind;
}
void solve()
{
S[1] = A[1];
for(int i=2; i<=N; i++) S[i] = A[i]^S[i-1];
insert(T, 0, 0);
int sol = -INF, start, stop;
for(int i=1; i<=N; i++) {
int p = que(T, S[i]);
if( sol < S[i]^S[p] ) sol = S[i]^S[p], start = p+1, stop = i;
insert(T, S[i], i);
}
printf("%d %d %d", sol, start, stop);
}
int main()
{
freopen(inf,"r",stdin); freopen(outf,"w",stdout);
read(); solve();
return 0;
}