Cod sursa(job #186550)

Utilizator floringh06Florin Ghesu floringh06 Data 28 aprilie 2008 11:27:10
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "xormax.in"
#define FOUT "xormax.out"
#define MAX_N 103000
#define MAX_B 21

int H[4 << MAX_B];  
int N, s, BEST;
   
    void update(int x, int ind) 
    {  
         int q = 0;  
     
         for (int i = MAX_B - 1; i >= 0; --i) 
         {  
             if (x & (1 << i)) q = (q + 1) << 1;  
                else q = (q << 1) | 1;  
            
             H[q] = ind;  
         }  
    }  
   
    int main() 
    {  
        freopen(FIN, "r", stdin);  
        freopen(FOUT, "w", stdout);  
   
        memset (H, -1, sizeof (H));
     
        update(0, 0), scanf("%d", &N);  
 
        int u = 1, v = 1, i, j;  
     
        for (i = 1; i <= N; ++i)
        {  
            int x, y = 0, q = 0;
           
            scanf("%d", &x);  
            
            s ^= x;  
   
            for (j = MAX_B - 1; j >= 0; --j) 
            {  
                int V[2], c = (s & (1 << j)) != 0;  
                
                V[0] = (q << 1) | 1, V[1] = (q + 1) << 1;  
             
                if (H[V[!c]] != -1) c = !c;  
                q = V[c];  
                if (c) y |= 1 << j;  
            }  
   
            if ((s ^ y) > BEST) 
                   BEST = s ^ y, u = H[q] + 1, v = i;  
  
   
            update(s, i);  
         }  
   
         printf("%d %d %d\n", BEST, u, v);  
   
         return 0;  
    }