Cod sursa(job #1045663)

Utilizator ion824Ion Ureche ion824 Data 1 decembrie 2013 20:57:44
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<fstream>
using namespace std;
typedef struct T{
        int ind;
        T* next[2];
        T(){
            next[0]=next[1]=NULL;
            ind=0;
            }
        }*Trie;
Trie Tr;
const int NMAX = 100003;
int S[NMAX],i,N,st,dr,ans;
int conf[NMAX];

void insert(Trie Tr, int conf[], int l){
     
     for(int j=0;j<=l;++j)
     {
         if(!Tr->next[conf[j]])
           Tr->next[conf[j]] = new T;
         Tr=Tr->next[conf[j]];
     }
     Tr->ind=i;
}

void Update(Trie Tr,int conf[], int l){
     
     for(int j=0;j<=l;++j)
       if(Tr->next[conf[j]^1])
         Tr=Tr->next[conf[j]^1];
       else Tr=Tr->next[conf[j]];
     
     if((S[Tr->ind] ^ S[i]) > ans)
     {
       ans = S[Tr->ind] ^ S[i];
       st = Tr->ind+1;
       dr = i;
     }        
}

int main(){
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    int bit;
    bool zero=0;
    
    cin>>N;
    Tr = new T;
    
    for(i=1;i<=N && !zero;++i)
    {
      cin>>S[i];
      S[i]^=S[i-1];
      //if(S[i]==0){ zero=1; st=1; dr=i; }
      
      for(bit=0;bit<=21;++bit)
        if(S[i] & (1<<bit)) conf[21-bit]=1;
          else conf[21-bit]=0;
       
       insert(Tr, conf, 21);
       Update(Tr, conf, 21);                   
    }
   
   //if(zero) cout<<0<<' '<<1<<' '<<dr<<'\n';
      if(ans==0) cout<<0<<' '<<1<<' '<<N;
      else cout<<ans<<' '<<st<<' '<<dr<<'\n';
        
 return 0;   
}