Pagini recente » Cod sursa (job #1154858) | Cod sursa (job #1094585) | Cod sursa (job #949566) | Cod sursa (job #2344618) | Cod sursa (job #87660)
Cod sursa(job #87660)
#include <stdio.h>
#include <string.h>
#define NMAX 100002
long int TR[NMAX*22][2],i,j,k,n,v[NMAX],poz[NMAX],FIN[NMAX],sol[3],p,nst,len;
long int cv[NMAX];
void query()
{
long int nod,bit,sum,s,x,y,i;
sum=0;
for (nod=0,i=len;i;i--)
{
bit=cv[len-i];
if (FIN[nod]) {
s=sum^k;
x=poz[nod]+1;y=p;
if (s>sol[0]) {sol[0]=s;sol[1]=x;sol[2]=y;}
if ((s==sol[0])&&(y<sol[2])) {sol[1]=x;sol[2]=y;}
if ((s==sol[0])&&(y==sol[2])&&(x>sol[1])) sol[1]=x;
}
if (TR[nod][!bit]) {
nod=TR[nod][!bit];
if (!bit==1) sum=sum+ (1 << i);
}
else if (TR[nod][bit]) {
nod=TR[nod][bit];
if (bit==1) sum=sum+ (1 << (len - i -1));
}
else break;
}
}
void baga_trie()
{
long int nod=0,i;
for (i=len;i;i--)
{
if (!TR[nod][ cv[i] ]) TR[nod][ cv[i] ]=++nst;
nod=TR[nod][ cv[i] ];
if (i==1) {FIN[nod]=1;poz[nod]=p;}
}
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;i++)
{
scanf("%ld",&k);
v[i]=v[i-1]^k;
}
for (i=1;i<=n;i++)
{
for (k=v[i],j=1;k;k/=2,j++);
if (j-1>len) len=j-1;
}
len++;
FIN[0]=1;nst=0;
for (i=1;i<=n;i++)
{
memset(cv,0,sizeof(cv));
k=v[i];
p=i;
for (j=1;k;k/=2,j++) cv[j]=k%2;
k=v[i];
baga_trie();
query();
}
printf("%ld %ld %ld",sol[0],sol[1],sol[2]);
return 0;
}