Pagini recente » Cod sursa (job #441496) | Cod sursa (job #2270348) | Cod sursa (job #229044) | Cod sursa (job #3239010) | Cod sursa (job #24779)
Cod sursa(job #24779)
#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[nmax],trie[nrmax],lung,f_st[nrmax],f_dr[nrmax],sol,inc,sf,sir[nmax];
void insert(int long,int long);
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(f_st,nil,sizeof(f_st));
memset(f_dr,nil,sizeof(f_dr));
insert(xor[1],1);
}
void insert(int long x,int long poz)
{int long j,key=1;
for(j=20;j>=0;j--)
if(x&(1<<j))
{if(f_dr[key]<0)
f_dr[key]=++lung;
key=f_dr[key];
}
else
{if(f_st[key]<0)
f_st[key]=++lung;
key=f_st[key];
}
if(!trie[key])
trie[key]=poz;
}
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(f_dr[key]>0)
key=f_dr[key];
else
key=f_st[key];
else
if(f_st[key]>0)
key=f_st[key];
else
key=f_dr[key];
return trie[key];
}
int long rezolva()
{int long i,d;
init();
for(i=2;i<=n;i++)
{if(sol<xor[i])
sol=xor[i];
d=search(~xor[i]);
if(xor[d]^xor[i]<sol)
{sol=xor[d]^xor[i];
inc=d+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;
}