Cod sursa(job #214741)

Utilizator raduzerRadu Zernoveanu raduzer Data 15 octombrie 2008 19:51:09
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <cstdio>

const int MAX_N = 100010;

int n, max, sol, s, nsol, s1, s2;
int b, p, x, z, nod;
int a[MAX_N], t[MAX_N][2], c[32], r[MAX_N];

void search(int i)
{
     int nod = 1, put = 1 << b;
     while (put > 1)
     {
           put >>= 1;
           
           int q = a[i] & put;
           
           if (q) q = 1;
           
           if (t[nod][1-q])
           {
                nod = t[nod][1-q];
                s += put;
           }
           else nod = t[nod][q];
     }
     nsol = r[nod];
}

void construct()
{
     int i, j;
     
     for (i = 1; i <= n; ++i) 
     {
        x = a[i]; 
        p = 0;
        
        while (x)
        {
              c[++p] = x % 2;
              x /= 2;
        }
        for (j = p + 1; j <= b; ++j) c[j] = 0;
        
        nod = 1;
        for (j = b; j > 0; --j)
        {
            if (t[nod][c[j]]) nod = t[nod][c[j]];
            else
            {
                ++z;
                t[nod][c[j]] = z;
                nod = z;
            }
            
            r[nod] = i;
        }
     }
}

int main()
{
    int i, j;
    
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    
    scanf("%d", &n);
    
    for (i = 1; i <= n; ++i) scanf("%d",  &a[i]);
    
    max = a[1];
    for (i = 2; i <= n; ++i) 
    {
        a[i] ^= a[i-1];
        if (max < a[i]) 
        {
            max = a[i];
            s1 = 1; 
            s2 = i;
        }
    }

    while (max)
    {
          ++b;
          max /= 2;
    }

    z = 1;
    
    construct();
    
    for (i = 0; i <= n; ++i)
    {
        s = 0;
        search(i);
        if (s > sol) 
        {
              sol = s;
              s1 = i + 1;
              s2 = nsol;
        }
    }   
    
    printf("%d %d %d\n", sol, s1, s2);
    
    return 0;
}