Pagini recente » Cod sursa (job #174744) | Cod sursa (job #1511229) | Istoria paginii utilizator/vladroman | Statistici Tony Vulpe (Tony102) | Cod sursa (job #1711700)
#include <cstdio>
#include <cstring>
#define MAXBIT 23
#define INF 100000
int biti[MAXBIT+1];
int max=-1,left,right,i;
struct Trie{
int poz;
Trie *fii[2];
Trie(){
poz=INF;
memset(fii,0,sizeof(fii));
};
};
Trie *T=new Trie;
void insert_Trie(Trie *nod,int pos){
if(pos>=0){
if(nod->fii[biti[pos]]==0)
nod->fii[biti[pos]]=new Trie;
insert_Trie(nod->fii[biti[pos]],pos-1);
}
else
nod->poz=i;
}
void Max_Trie(Trie *nod,int pos,int nr){
if(pos==-1){
if(max<nr){
max=nr;
left=nod->poz;
right=i;
}
}
else{
if(biti[pos]==0){
if(nod->fii[1]!=0)
Max_Trie(nod->fii[1],pos-1,nr+(1<<pos));
else
if(nod->fii[0]!=0)
Max_Trie(nod->fii[0],pos-1,nr);
}
else{
if(nod->fii[0]!=0)
Max_Trie(nod->fii[0],pos-1,nr+(1<<pos));
else
if(nod->fii[1]!=0)
Max_Trie(nod->fii[1],pos-1,nr);
}
}
}
int main(){
FILE*fi,*fout;
int n,x,j;
fi=fopen("xormax.in" ,"r");
fout=fopen("xormax.out" ,"w");
fscanf(fi,"%d" ,&n);
i=0;
insert_Trie(T,MAXBIT-1);
for(i=1;i<=n;i++){
fscanf(fi,"%d" ,&x);
for(j=0;j<MAXBIT;j++){
biti[j]=((x&1)^biti[j]);
x=(x>>1);
}
Max_Trie(T,MAXBIT-1,0);
insert_Trie(T,MAXBIT-1);
}
fprintf(fout,"%d %d %d" ,max,left+1,right);
fclose(fi);
fclose(fout);
return 0;
}