Pagini recente » Cod sursa (job #1580843) | Cod sursa (job #2502172) | Cod sursa (job #614413) | Cod sursa (job #2434870) | Cod sursa (job #127419)
Cod sursa(job #127419)
#include <cstdio>
#define INF "xormax.in"
#define OUF "xormax.out"
#define NMAX 100002
#define PMAX 20
using namespace std;
int t[(1<<(PMAX+2))];
void insert(int x,int poz)// x=suma xor, poz= poz
{
int j,p;
//printf("insert %d:\n",x);
p=1;
for(j=PMAX;j>=0;--j)
if(x&(1<<j)) // bitul j este 1
{
//printf("1 ");
t[p]=0;
p=2*p+1;
}
else
{
//printf("0 ");
t[p]=0;
p=2*p;
}
//printf("\n");
t[p]=poz;
}
int query(int x)//returneaza cea mai buna pozitie pentru suma xor x
{
int j,p;
p=1;
for(j=PMAX;j>=0;--j)
if(x&(1<<j))
{
if(t[2*p]>=0) p=2*p;
else p=2*p+1;
}
else
{
if(t[2*p+1]>=0) p=2*p+1;
else p=2*p;
}
if(t[p]>0) return t[p];
return 0;
}
int main()
{
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
int xsum[NMAX],x,i,n;
int solsum,st,dr;
fscanf(in,"%d",&n);
for(i=0;i<(1<<PMAX+2);++i) t[i]=-1;
xsum[0]=0;
insert(0,0);
solsum=0;st=0;dr=0;
for(i=1;i<=n;++i)
{
fscanf(in,"%d",&x);
if(x>2097151) xsum[NMAX+100000]=16;
xsum[i]=(xsum[i-1]^x);
insert(xsum[i],i);
x=0;
x=query(xsum[i]);
// printf("%d %d %d\n",i,x,(xsum[i]^xsum[x]));
if((xsum[i]^xsum[x])>solsum)
{
solsum=(xsum[i]^xsum[x]);
st=x+1;dr=i;
}
}
//for(i=1;i<(1<<(PMAX+2));++i) printf("%d ",t[i]);
fprintf(out,"%d %d %d\n",solsum,st,dr);
if(dr==0) xsum[NMAX+100000]=16;
fclose(in);fclose(out);
return 0;
}