Cod sursa(job #1711671)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 31 mai 2016 21:52:22
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <cstring>
#define MAXBIT 22
#define INF 100000
int biti[MAXBIT+1],bitx[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
        if(nod->poz==INF)
         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(max==nr&&(left>nod->poz||(left==nod->poz&&right>i))){
               left=nod->poz;
               right=i;
           }
    }
    else{
        if(nod->fii[1]!=0){
            if(bitx[pos]==0)
                Max_Trie(nod->fii[1],pos-1,nr+(1<<pos));
            else
                Max_Trie(nod->fii[1],pos-1,nr);
        }
        else
           if(nod->fii[0]!=0){
              if(bitx[pos]==1)
                  Max_Trie(nod->fii[0],pos-1,nr+(1<<pos));
              else
                  Max_Trie(nod->fii[0],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);
   insert_Trie(T,MAXBIT-1);
   for(i=1;i<=n;i++){
       fscanf(fi,"%d" ,&x);
       for(j=0;j<MAXBIT;j++){
           bitx[j]=(x&1);
           biti[j]=(bitx[j]^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;
}