Pagini recente » Cod sursa (job #323408) | Cod sursa (job #2966987) | Cod sursa (job #645763) | Cod sursa (job #1813763) | Cod sursa (job #3170086)
#include <fstream>
using namespace std;
int n,k,x,y,p,poz,val,bit,maxi,st,dr,v[100005];
struct trie
{
int ind,pz,cp[2];
}w[1<<21];
int main()
{
ifstream f("xormax.in");
ofstream g("xormax.out");
f>>n;
for(int i=1; i<=21; i++)
{
k++;
w[k].ind=0;
w[k].pz=0;
w[k].cp[0]=k+1;
}
w[k].cp[0]=0;//am adaugat 0 in trie
for(int i=1; i<=n; i++)
{
f>>v[i];
v[i]=v[i] xor v[i-1];
x=v[i];
p=1<<20;
poz=0;
while(p>=1)
{
bit=(x/p)%2;
//g<<bit;
if(w[poz].cp[1-bit]) poz=w[poz].cp[1-bit];
else poz=w[poz].cp[bit];
p/=2;
}
//g<<'\n';
//g<<x<<" "<<w[poz].ind<<'\n';
val=x^w[poz].ind;
if(val>maxi)
{
maxi=val;
dr=i;
}
p=1<<20;
poz=0;
val=0;
while(p>=1)
{
bit=(x/p)%2;
val*=2;
val+=bit;
if(w[poz].cp[bit]) poz=w[poz].cp[bit];
else
{
w[poz].cp[bit]=k+1;
k++;
w[k].ind=val;
w[k].pz=i;
poz=k;
}
p/=2;
}
}
for(int i=0; i<dr; i++)
{
if(v[i] xor v[dr] == maxi) st=i+1;
}
g<<maxi<<" "<<st<<" "<<dr;
return 0;
}