Cod sursa(job #132098)

Utilizator vlad_popaVlad Popa vlad_popa Data 5 februarie 2008 00:06:42
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 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 (st > trie[nod][0] + 1)
            {
                st = trie[nod][0] + 1;
                dr = i;
            }
            else if (st == trie[nod][0] + 1)
                if (dr > i)
                    dr = i;
    }
    
    printf ("%d %d %d\n", maxim, st, dr);
}

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