Pagini recente » Cod sursa (job #927409) | Cod sursa (job #3178527) | Solutii preONI 2006 - Runda a 3-a | Cod sursa (job #1044292) | Cod sursa (job #464827)
Cod sursa(job #464827)
#include <cstdio>
#define N 100005
struct Nod
{
Nod *v[2];
Nod()
{
v[0]=v[1]=0;
}
};
int n;
int a[N];
Nod *t=new Nod;
int xmax,start,stop;
const int M=1<<20;
inline void citire()
{
scanf("%d",&n);
for(int i=1; i<=n; ++i)
{
scanf("%d",&a[i]);
a[i]^=a[i-1];
}
}
void add(Nod *x,int nr,int mask)
{
if(mask==0)
return;
if((nr&mask)==0)
{
if(x->v[0]==0)
x->v[0]=new Nod;
add(x->v[0],nr,mask>>1);
}
else
{
if(x->v[1]==0)
x->v[1]=new Nod;
add(x->v[1],nr,mask>>1);
}
}
int find(Nod *x,int nr,int mask)
{
if(mask==0)
return 0;
if((nr&mask)==0)
{
if(x->v[1]!=0)
return (mask|find(x->v[1],nr,mask>>1));
else
return find(x->v[0],nr,mask>>1);
}
else
{
if(x->v[0]!=0)
return (mask|find(x->v[0],nr,mask>>1));
else
return find(x->v[1],nr,mask>>1);
}
}
inline void rezolva()
{
add(t,0,M);
int aux;
for(int i=1; i<=n; ++i)
{
aux=find(t,a[i],M);
if(aux>xmax)
{
xmax=aux;
stop=i;
}
add(t,a[i],M);
}
if(xmax==0)
{
printf("0 1 1\n");
return;
}
aux=xmax^a[stop];
start=stop-1;
for(; a[start]!=aux; --start)
;
++start;
printf("%d %d %d\n",xmax,start,stop);
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
citire();
rezolva();
return 0;
}