Cod sursa(job #253198)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 15:47:08
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
   #include <stdio.h>  
   #include <algorithm>  
   using namespace std;  
     
   #define maxl 100010  
     
   int n,m,i,j,k,last,p,q,rez,val,w,pas,x,y;  
   int a[maxl],v[maxl];  
   int fol [1 << 22];  
   int trie[50 * maxl][2];  
   int p2[20], sol[20];  
     
   void tr() {  
        p = 0;  
        for (i = 0; i <= 20; i++) {  
            k = v[w] & (1<< (20 - i));  
            if (k != 0) k = 1;  
     
            if (trie[p][k] == 0) {  
               trie[p][k] = ++last;  
               p = last;  
            }  
            else p = trie[p][k];  
        }  
   }      
     
   void dfs(int p, int q) {  
        pas++;  
    
        if (rez > val) {  
           val = rez;  
           for (i = 0; i <= 20; i++)  
               sol[i] = val & p2[i];  
        }  
     
        if (rez < sol[pas]) {  
           pas--;  
           return;  
        }  
     
        if (trie[p][0] != 0) {  
           if (trie[q][1] != 0) {  
               rez += p2[pas]; y += p2[pas];  
               dfs(trie[p][0], trie[q][1]);  
               rez -= p2[pas]; y -= p2[pas];  
           }  
          else  
              if (trie[q][0] != 0) dfs(trie[p][0], trie[q][0]);  
              else dfs(trie[p][0], q);  
       }  
    
       if (trie[p][1] != 0)  
       {  
          if (trie[q][0] != 0) {  
              rez += p2[pas]; x += p2[pas];  
              dfs(trie[p][1], trie[q][0]);  
              rez -= p2[pas]; x -= p2[pas];  
           }  
           else {  
                x += p2[pas];  
                if (trie[q][1] != 0) {  
                   y += p2[pas];  
                   dfs(trie[p][1], trie[q][1]);  
                   y -= p2[pas];  
                }  
                else dfs(trie[p][1], q);  
                x -= p2[pas];  
           }  
       }  
    
    
       pas--;  
  }  
    
  int poz(int x) {  
      for (i = 0; i <= n; i++)  
          if (v[i] == x) return i;  
  }  
    
  int main() {  
      freopen("xormax.in","r",stdin);  
      freopen("xormax.out","w",stdout);  
        
      scanf("%d", &n);  
      for (w = 1; w <= n; w++) {  
          scanf("%d", &a[w]);  
          v[w] = v[w - 1] ^ a[w];  
          tr();  
      }  
      w = 0; tr();  
      for (w = n; w >= 1; w--)  
          fol[v[w]] = w;  
    
      for (i=0; i<=20; i++)  
          p2[i] = 1 << (20 - i);  
    
      rez = 0; val = 0; pas = -1; x = 0; y = 0;  
      dfs(0,0);  
    
      if (n == 1) {  
         printf("%d %d %d\n",a[1],1,1);  
         return 0;  
      }  
    
      x = 2147000000; y = x; fol[0] = 1;  
      for (i = 1; i <= n; i++) {  
          k = val ^ v[i];  
          if (fol[k] && fol[k] <= i) {  
             y = i;  
             break;  
          }  
      }  
      for (i = 1; i <= y; i++)  
          if ((val ^ v[y]) == v[i]) x = i;   
        
      printf("%d %d %d\n", val, x + 1, y);  
    
      return 0;  
 }