Pagini recente » Cod sursa (job #2443561) | Cod sursa (job #1279905) | Cod sursa (job #1873471) | Cod sursa (job #409362) | Cod sursa (job #1520851)
#include<cstdio>
#define pow2 1048576
int vc[10000000],v[100010],pow[21],nr;
char vec[21];
struct trie
{trie *fii[3];
trie()
{for (int i=0;i<=2;i++)
fii[i]=NULL;
}
};
trie *T=new trie;
void insert(trie *nod,char *s)
{if(*s==NULL)
return ;
if(nod->fii[*s]==NULL)
nod->fii[*s]=new trie;
insert(nod->fii[*s],s+1);
}
int xoreala(trie *nod,char *s,int a)
{if(*s==NULL)
return 0;
if(nod->fii[*s]==NULL)
{if(vec[20-a]==2)
return xoreala(nod->fii[1],s+1,a-1);
else
{nr+=pow[a];
return xoreala(nod->fii[2],s+1,a-1);
}
}
else
{if(vec[20-a]==2)
nr+=pow[a];
return pow[a]+xoreala(nod->fii[*s],s+1,a-1);
}
}
int main ()
{freopen ("xormax.in","r",stdin);
freopen ("xormax.out","w",stdout);
int n,max=0,start,stop,i,j,x,y,z,p;
pow[0]=1;
for(i=1;i<=20;i++)
pow[i]=pow[i-1]*2;
scanf("%d",&n);
scanf("%d",&x);
v[1]=x;
x=pow2;
y=v[1];
for(j=20;j>=0;j--)
{if(y>=x)
{vec[20-j]=2;
y-=x;
}
else
vec[20-j]=1;
x/=2;
}
insert(T,vec);
max=v[1];
start=stop=1;
vc[v[1]]=1;
for(i=2;i<=n;i++)
{scanf("%d",&x);
for(j=0;j<=20;j++)
vec[j]=1;
v[i]=(x^v[i-1]);
vc[v[i]]=i;
p=pow2;
y=v[i];
for(j=20;j>=0;j--)
{if(y<p)
vec[20-j]=2;
else
y-=p;
p/=2;
}
nr=0;
z=xoreala(T,vec,20);
if(z>max)
{max=z;
stop=i;
start=vc[nr]+1;
}
if(v[i]>max)
{max=v[i];
start=1;
stop=i;
}
for(j=0;j<=20;j++)
vec[j]=1;
x=pow2;
y=v[i];
for(j=20;j>=0;j--)
{if(y>=x)
{vec[20-j]=2;
y-=x;
}
else
vec[20-j]=1;
x/=2;
}
insert(T,vec);
}
printf("%d %d %d",max,start,stop);
return 0;
}