Pagini recente » Cod sursa (job #649578) | Cod sursa (job #1837037) | Cod sursa (job #2218480) | Cod sursa (job #2628722) | Cod sursa (job #1711977)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int num[23];
int i, max, st, fin;
struct Trie{
int poz;
Trie *fii[2];
Trie(){
poz=1000000000;
fii[0]=fii[1]=0;
}
};
Trie *T=new Trie;
void Trie_insert(Trie *nod, int ind){
if(ind<0)
nod->poz=i;
else{
if(nod->fii[num[ind]]==0)
nod->fii[num[ind]]=new Trie;
Trie_insert(nod->fii[num[ind]], ind-1);
}
}
void Trie_find_max(Trie *nod, int val, int ind){
if(ind==-1){
if(max<val){
max=val;
st=nod->poz;
fin=i;
}
}
else{
if(num[ind]==0){
if(nod->fii[1]!=0)
Trie_find_max(nod->fii[1], val+(1<<ind), ind-1);
else if(nod->fii[0]!=0)
Trie_find_max(nod->fii[0], val, ind-1);
}
else{
if(nod->fii[0]!=0)
Trie_find_max(nod->fii[0], val+(1<<ind), ind-1);
else if(nod->fii[1]!=0)
Trie_find_max(nod->fii[1], val, ind-1);
}
}
}
int main(){
int n;
FILE*fi,*fo;
fi=fopen("xormax.in","r");
fo=fopen("xormax.out","w");
fscanf(fi,"%d", &n);
max=-1;
i=0;
Trie_insert(T, 22);
for(i=1;i<=n;i++){
int x;
fscanf(fi,"%d", &x);
for(int j=0;j<=22;j++){
num[j]=num[j]^(x%2);
x/=2;
}
Trie_find_max(T, 0, 22);
Trie_insert(T, 22);
}
fprintf(fo,"%d %d %d", max, st, fin);
fclose(fi);
fclose(fo);
return 0;
}