Pagini recente » Cod sursa (job #1396462) | Cod sursa (job #3153272) | Cod sursa (job #3133243) | Cod sursa (job #1218415) | Cod sursa (job #24789)
Cod sursa(job #24789)
#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,xorr[nmax],trie[nrmax],lung,fst[nrmax],fdr[nrmax],sol,inc,sf,sir[nmax];
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;
xorr[1]=sir[1];
for(i=2;i<=n;i++)
xorr[i]=xorr[i-1]^sir[i];
sol=xorr[1];
inc=1; sf=1;
lung=1;
memset(fst,nil,sizeof(fst));
memset(fdr,nil,sizeof(fdr));
insert(xorr[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(~xorr[i]);
if((xorr[d]^xorr[i])<sol)
{sol=xorr[d]^xorr[i];
inc=d+1;
sf=i;
}
if(sol<xorr[i])
{sol=xorr[i];
inc=1;
sf=i;
}
insert(xorr[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;
}