Cod sursa(job #220689)

Utilizator Mishu91Andrei Misarca Mishu91 Data 11 noiembrie 2008 23:59:24
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <cstring>

#define MAX_N 100005
#define MAX_B 21

int H[4 << MAX_B];  
int N, Sol;
   
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("xormax.in", "rt", stdin);
    freopen("xormax.out", "wt", stdout);
   
    memset (H, -1, sizeof (H));
    update(0, 0);

    scanf("%d", &N);
 
    int start = 1, end = 1, s = 0;
    for (int i = 1; i <= N; ++i)
    {
        int x, y = 0, q = 0;
           
        scanf("%d", &x);
            
        s ^= x;
   
        for (int 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) > Sol)
            Sol = s ^ y, start = H[q] + 1, end = i;

         update(s, i);
    }
   
    printf("%d %d %d\n", Sol, start, end);
}