Pagini recente » Cod sursa (job #1347559) | Cod sursa (job #1107190) | Istoria paginii runda/oni2013_ziua2/clasament | Istoria paginii runda/3423523451/clasament | Cod sursa (job #447829)
Cod sursa(job #447829)
#include <stdio.h>
#define NMAX 100005
int n,A[NMAX],act,sum[NMAX],best[NMAX],part,ant[NMAX];
int rez,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 ;
}
int tip=val & 1<<(poz-1);
if (tip)
tip=1;
if (nod->fiu[1 ^ tip])
{
part^=1<<(poz-1);
tip=1 ^ tip;
}
answer(nod->fiu[tip],val,poz-1);
}
void solve()
{
int i;
for (i=1; i<=n; i++)
{
act=i;
sum[i]=sum[i-1] ^ A[i];
ins(T,sum[i],22);
part=0;
answer(T,sum[i],22);
best[i]=part;
if (rez<best[i])
rez=best[i], st=ant[i]+1, dr=i;
if (rez<A[i])
rez=A[i], st=i, dr=i;
}
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
read();
solve();
printf("%d %d %d\n",rez,st,dr);
return 0;
}