Cod sursa(job #1711700)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 31 mai 2016 23:23:57
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#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;
}