Cod sursa(job #214771)

Utilizator raduzerRadu Zernoveanu raduzer Data 15 octombrie 2008 21:11:50
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 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*32][2], c[32], r[MAX_N*32];

void search(int i)
{
     int nod = 1, put = 1 << b, q;
     while (put > 1)
     {
           put >>= 1;
           
           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 solve()
{
     int i, j;
     
     for (i = 0; i <= n; ++i) 
     {
         if (i)
         {
          s=0;
          search(i);
          if (s>sol)
            {
             sol=s;
             s1=nsol+1;
             s2=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];
    for (i = 2; i <= n; ++i) 
    {
        a[i] ^= a[i-1];
        if (sol < a[i]) 
            sol = a[i];
    }

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

    z=1;
    ++b;
    
    sol=0;
    solve();
     
    printf("%d %d %d\n", sol, s1, s2);
    
    return 0;
}