Pagini recente » Cod sursa (job #1545898) | Monitorul de evaluare | reluare_kidsim2 | Cod sursa (job #816751) | Cod sursa (job #1532838)
#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,x,ok,ras,ma,k,p1,p2,a[100004];
struct trie
{
int val;
trie *urm[2];
trie()
{
val=0;
urm[0]=urm[1]=0;
}
}*init,*nr,*q;
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++)
{
scanf("%d ",&x);
a[i]=a[i-1]^x;
}
nr=new trie;
init=nr;
k=-1;
for (int j=20; j>=0; j--)
{
ok=(a[i]&(1<<j))>>j;
q=new trie;
nr->urm[ok]=q;
nr=q;
}
nr->val=1;
for (int i=2; i<=n; i++)
{
nr=init;
for (int j=20; j>=0; j--)
{
ok=(a[i]&(1<<j))>>j;
if(nr->urm[ok^1])nr=nr->urm[ok^1];
else nr=nr->urm[ok];
}
ras=nr->val;
if(ma<a[i]^a[ras])
{
ma=a[i]^a[ras];
p2=i;
p1=ras+1;
}
nr=init;
for (int j=20; j>=0; j--)
{
ok=(a[i]&(1<<j))>>j;
if(nr->urm[ok])nr=nr->urm[ok];
else
{
q=new trie;
nr->urm[ok]=q;
nr=q;
}
}
nr->val=i;
}
printf("%d %d %d",ma,p1,p2);
return 0;
}