Pagini recente » Cod sursa (job #1757242) | Cod sursa (job #1929476) | Cod sursa (job #245018) | Cod sursa (job #2038494) | Cod sursa (job #24786)
Cod sursa(job #24786)
#include<stdio.h>
#include<fstream.h>
#define fin "xormax.in"
#define fout "xormax.out"
//#define nil -1
//#define nmax 100005
//#define nrmax 2100000
int long n,xor[100000],trie[2100000],lung,fst[2100000],fdr[2100000],sol,inc,sf,sir[100000];
void insert(int long x,int long poz)
{int long j,key=1;
for(j=20;j>=0;j--)
if(x&(1<<j))
{if(fdr[key]<0)
fdr[key]=++lung;
key=fdr[key];
}
else
{if(fst[key]<0)
fst[key]=++lung;
key=fst[key];
}
trie[key]=poz;
}
void init()
{int long i;
xor[1]=sir[1];
for(i=2;i<=n;i++)
xor[i]=xor[i-1]^sir[i];
sol=xor[1];
inc=1; sf=1;
lung=1;
memset(fst,nil,sizeof(fst));
memset(fdr,nil,sizeof(fdr));
insert(xor[1],1);
}
int long search(int long x)//cauta trie[k] cel mai apropiat de x
{int long key=1,j;
for(j=20;j>=0;j--)
if(x&1<<j)
if(fdr[key]>0)
key=fdr[key];
else
key=fst[key];
else
if(fst[key]>0)
key=fst[key];
else
key=fdr[key];
return trie[key];
}
int long rezolva()
{int long i,d;
init();
for(i=2;i<=n;i++)
{d=search(~xor[i]);
if((xor[d]^xor[i])<sol)
{sol=xor[d]^xor[i];
inc=d+1;
sf=i;
}
if(sol<xor[i])
{sol=xor[i];
inc=1;
sf=i;
}
insert(xor[i],i);
}
return 0;
}
void afiseaza()
{freopen(fout,"w",stdout);
printf("%ld %ld %ld",sol,inc,sf);
fclose(stdout);
}
void citire()
{int long i;
freopen(fin,"r",stdin);
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%ld",&sir[i]);
}
int main()
{citire();
rezolva();
afiseaza();
return 0;
}