Pagini recente » Cod sursa (job #2105371) | Cod sursa (job #2447535) | Cod sursa (job #3257205) | Cod sursa (job #2506329) | Cod sursa (job #206717)
Cod sursa(job #206717)
#include<stdio.h>
#include<string.h>
#define M 20
#define N 100007
int mat[N][M+3],sum[N][M+3];
inline int funct(int w[]){
int i,nr=0;
for(i=0;i<=M;++i)
if(w[i]==1)
nr+=(1<<i);
return nr;
}
struct nod{
struct nod *st, *dr;
};
typedef struct nod*str;
void solv1(int nr,int w[]){
int i;
for(i=M;i>=0;--i)
if(nr&(1<<i))
w[i]=1;
else
w[i]=0;
}
void solv2(int w[],int y[],int t[]){
int i;
for(i=0;i<=M;++i)
t[i]=w[i]^y[i];
}
int main(){
int n,i,j,nr,max=-1,g,b[M+1],bb[M+1],p;
str s,u,m;
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
s=new nod;
u=s;
for(i=0;i<=M;i++){
m=new nod;
u->dr=NULL;
u->st=m;
u=m;
}
u->dr=NULL;
u->st=NULL;
for(i=1;i<=n;++i){
scanf("%d",&nr);
solv1(nr,mat[i]);
solv2(mat[i],sum[i-1],sum[i]);
u=s;
for(j=M;j>=0;--j)
if(sum[i][j]==1){
if(!(u->st)){
m=new nod;
u->st=m;
m->st=NULL;
m->dr=NULL;
u=m;
}
else
u=u->st;
}
else
if(!(u->dr)){
m=new nod;
u->dr=m;
m->st=NULL;
m->dr=NULL;
u=m;
}
else
u=u->dr;
u=s;
for(j=M;j>=0;--j)
if(sum[i][j]==1){
if(u->st){
b[j]=1;
u=u->dr;
}
else{
b[j]=0;
u=u->st;
}
}
else
if(u->st){
u=u->st;
b[j]=1;
}
else{
u=u->st;
b[j]=0;
}
nr=funct(b);
if(nr>max){
max=nr;
for(j=0;j<=M;j++)
bb[j]=b[j]^sum[i][j];
p=i;
}
}
for(j=p-1;j>=0;--j){
g=1;
for(i=0;i<=M;i++)
if(sum[j][i]!=bb[i]){
g=0;
break;
}
if(g==1){
i=j+1;
break;
}
}
printf("%d %d %d\n",max,i,p);
fclose(stdout);
fclose(stdin);
return 0;
}