Pagini recente » Cod sursa (job #1137846) | Cod sursa (job #1535302) | Cod sursa (job #2902753) | Cod sursa (job #2291874) | Cod sursa (job #132212)
Cod sursa(job #132212)
//xormax
#include<stdio.h>
FILE*fin=fopen("xormax.in","r");
FILE*fout=fopen("xormax.out","w");
#define maxc 20
#define maxn 100001
struct nod{struct nod * st, * dr;};
typedef struct nod*trie;
int n,a[maxn][maxc+1],sumx[maxn][maxc+1];
void to2(int nr,int w[])
{
int i;
for(i=maxc;i>=0;i--)
if(nr&(1<<i)) w[i]=1;
else w[i]=0;
}
int to10(int w[])
{
int i,nr=0;
for(i=0;i<=maxc;i++)
if(w[i]==1) nr+=(1<<i);
return nr;
}
void sxor(int w[],int y[],int t[])
{
int i;
for(i=0;i<=maxc;i++)
t[i]=w[i]^y[i];
}
int main()
{
int i,j,nr,best=-1,g,b[maxc+1],bb[maxc+1],p;
trie prim,ultim,nn;
fscanf(fin,"%d",&n);
for(i=0;i<=maxc;i++)
sumx[0][i]=0;
prim=new nod;ultim=prim;
for(i=0;i<=maxc;i++)
{
nn=new nod;
ultim->st=nn;
ultim->dr=NULL;
ultim=nn;
}
ultim->st=NULL;ultim->dr=NULL;
for(i=1;i<=n;i++)
{
fscanf(fin,"%d",&nr);
to2(nr,a[i]);
sxor(a[i],sumx[i-1],sumx[i]);
ultim=prim;
for(j=maxc;j>=0;j--)
if(sumx[i][j]==1) if(!(ultim->dr)){nn=new nod;ultim->dr=nn;nn->st=NULL;nn->dr=NULL;ultim=nn;}
else ultim=ultim->dr;
else if(!(ultim->st)){nn=new nod;ultim->st=nn;nn->st=NULL;nn->dr=NULL;ultim=nn;}
else ultim=ultim->st;
ultim=prim;
for(j=maxc;j>=0;j--)
if(sumx[i][j]==1) if(ultim->st){b[j]=1;ultim=ultim->st;}
else{b[j]=0;ultim=ultim->dr;}
else if(ultim->dr){b[j]=1;ultim=ultim->dr;}
else{b[j]=0;ultim=ultim->st;}
nr=to10(b);
if(nr>best)
{
best=nr;
for(j=0;j<=maxc;j++)
bb[j]=b[j]^sumx[i][j];
p=i;
}
}
for(j=p-1;j>=0;j--)
{
g=1;
for(i=0;i<=maxc;i++)
if(sumx[j][i]!=bb[i]){g=0;break;}
if(g==1){i=j+1;break;}
}
fprintf(fout,"%d%c%d%c%d%c",best,' ',i,' ',p,'\n');
fclose(fin);
fclose(fout);
return 0;
}