Cod sursa(job #143854)

Utilizator vlad_popaVlad Popa vlad_popa Data 26 februarie 2008 21:56:56
Problema Xor Max Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
//100
#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, st2, dr2;
    
    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 (N < 1000)
            if (trie[nod][0] + 1 > i)
                continue;
        st2 = trie[nod][0];
        dr2 = i;
        if (st2 + 1 > dr2)  st2 ^= dr2, dr2 ^= st2, st2 ^= dr2;
        ++ st2;
        
        if (maxim < temp)
        {
            maxim = temp;
            st = st2;
            dr = dr2;
        }
        else if (maxim == temp)
            if (dr > dr2)
            {
                st = st2;
                dr = dr2;
            }
            else if (dr == dr2)
                if (st < st2)
                    st = st2;
    }
    
    printf ("%d %d %d\n", maxim, st, dr);
}

int
 main ()
{
    freopen ("xormax.in", "rt", stdin);
    freopen ("xormax.out", "wt", stdout);
    
    read ();
    solve ();
    
    return 0;
}