Mai intai trebuie sa te autentifici.
Cod sursa(job #470498)
Utilizator | Data | 14 iulie 2010 11:08:11 | |
---|---|---|---|
Problema | Xor Max | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.77 kb |
#include<cstdio>
#define N 1<<17
#define M 1<<20
int val[M];
int s,nrn,maxas,n,pi,pf,maxv,xorr[N],a[N];
int f[M][2];
int check(int x,int put)
{
if(x&put)
return 1;
return 0;
}
void insert(int nod,int nb,int put,int poz)
{
if(put==0)
{
val[nod]=poz;
return;
}
if(f[nod][check(nb,put)])
{
insert(f[nod][check(nb,put)],nb,put/2,poz);
return;
}
f[nod][check(nb,put)]=++nrn;
insert(nrn,nb,put/2,poz);
}
void search(int nod,int nb,int put,int asem)
{
if(put==0)
{
if(asem>maxas)
maxas=asem;
return;
}
if(f[nod][check(nb,put)])
search(f[nod][check(nb,put)],nb,put/2,asem+1);
else
search(f[nod][1-check(nb,put)],nb,put/2,asem);
}
void solve(int nod,int nb,int put,int poz,int asem)
{
if(put==0)
{
if(asem==maxas)
{
if((xorr[poz]^xorr[val[nod]])>maxv && val[nod]<poz)
{
maxv=xorr[poz]^xorr[val[nod]];
pi=val[nod]+1;
pf=poz;
}
}
return;
}
if(f[nod][check(nb,put)])
solve(f[nod][check(nb,put)],nb,put/2,poz,asem+1);
else
solve(f[nod][1-check(nb,put)],nb,put/2,poz,asem);
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
s=a[1];
xorr[1]=s;
nrn=1;
insert(1,s,1<<20,1);
pi=1;
pf=1;
maxv=0;
for(int i=2;i<=n;i++)
{
s^=a[i];
xorr[i]=s;
insert(1,s,1<<20,i);
int sp=0;
for(int j=0;j<=20;j++)
if(!(s&(1<<j)))
sp+=(1<<j);
maxas=0;
search(1,sp,1<<20,0);
solve(1,sp,1<<20,i,0);
}
printf("%d %d %d",maxv,pi,pf);
return 0;
}