Pagini recente » Cod sursa (job #2907565) | Cod sursa (job #580212) | Cod sursa (job #501651) | Cod sursa (job #2457086) | Cod sursa (job #575888)
Cod sursa(job #575888)
#include <stdio.h>
#define NMAX 100005
int n,A[NMAX],act,sum[NMAX],best[NMAX],ant[NMAX];
int rez=-1,st,dr;
struct trie
{
int cnt;
trie *fiu[2];
trie()
{
cnt=0;
fiu[0]=fiu[1]=0;
}
};
trie *T=new trie;
void read()
{
scanf("%d",&n);
int i;
for (i=1; i<=n; i++)
scanf("%d",&A[i]);
}
void ins(trie *nod,int val,int poz)
{
if (poz==0)
{
nod->cnt=act;
return ;
}
int tip=val & 1<<(poz-1);
if (tip)
tip=1;
if (nod->fiu[tip]==0)
nod->fiu[tip]=new trie;
ins(nod->fiu[tip],val,poz-1);
}
void answer(trie *nod,int val,int poz)
{
if (poz==0)
{
ant[act]=nod->cnt;
return ;
}
if (nod->fiu[0]==0 && nod->fiu[1]==0)
return ;
int tip=val & 1<<(poz-1);
if (tip)
tip=1;
if (nod->fiu[1 ^ tip])
tip=1 ^ tip;
answer(nod->fiu[tip],val,poz-1);
}
void solve()
{
int i;
ins(T,sum[0],22);
for (i=1; i<=n; i++)
{
act=i;
sum[i]=sum[i-1] ^ A[i];
answer(T,sum[i],22);
best[i]=sum[i] ^ sum[ant[i]];
if (rez<best[i])
rez=best[i], st=ant[i]+1, dr=i;
ins(T,sum[i],22);
}
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
read();
solve();
printf("%d %d %d\n",rez,st,dr);
return 0;
}