Cod sursa(job #132130)

Utilizator vlad_popaVlad Popa vlad_popa Data 5 februarie 2008 10:09:29
Problema Xor Max Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>  
   
#define NMAX 100001  
int N, M;  
int V[NMAX], X[NMAX];  
int trie[NMAX*21][2];  
void Update_Trie (int x, int poz)  
{  
    int i, bit, nod = 0;  
    for (i = 20; i >= 0; -- i)  
    {  
        bit = (x & (1 << i)) != 0;  
        if (!trie[nod][bit])  
        trie[nod][bit] = ++ M;  
        nod = trie[nod][bit];  
    }  
    trie[nod][0] = poz;  
}
  
void read ()  
{  
    scanf ("%d\n", &N);  
      
    int i;  
    for (i = 1; i <= N; ++ i)  
    {  
        scanf ("%d ", V + i);  
        X[i] = X[i-1] ^ V[i];  
    }  
}  
   
void solve ()  
{  
    int i, j, maxim = -1, nod, bit, temp;  
    int st, dr;  
      
    for (i = N; i >= 0; -- i)  
        Update_Trie (X[i], i);  
          
    for (i = 0; i <= N; ++ i)  
    {  
        nod = temp = 0;  
        for (j = 20; j >= 0; -- j)  
        {  
            bit = (X[i] & (1 << j)) != 0;  
            bit ^= 1;  
              
            if (trie[nod][bit] > 0)  
            {  
                nod = trie[nod][bit];  
                temp += (1 << j);  
            }  
            else if (!trie[nod][bit])  
                nod = trie[nod][1-bit];  
        }  
          
        if (trie[nod][0] + 1 > i)  
            continue;  
          
        if (maxim < temp)  
        {  
            maxim = temp;  
            st = trie[nod][0] + 1;  
            dr = i;  
        }  
        else if (maxim == temp)  
            if (dr > i)  
            {  
                st = trie[nod][0] + 1;  
                dr = i;  
            }  
            else if (dr == i)  
                if (st < trie[nod][0] + 1)  
                    st = trie[nod][0] + 1;  
    }  
      
    printf ("%d %d %d\n", maxim, st, dr);  
}  
  
int  
 main ()  
{  
    freopen ("xormax.in", "rt", stdin);  
    freopen ("xormax.out", "wt", stdout);  
       
    read ();  
    solve ();  
      
    return 0;  
}