Cod sursa(job #214749)

Utilizator raduzerRadu Zernoveanu raduzer Data 15 octombrie 2008 20:15:21
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 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]);
    
    sol = a[1];
    s1 = 1;
    s2 = 1;
    for (i = 2; i <= n; ++i) 
    {
        a[i] ^= a[i-1];
        if (sol < a[i]) 
        {
            sol = a[i];
            s1 = 1; 
            s2 = i;
        }
    }

    while ( (1<<(b+1)) <= sol )
          ++b;


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