Cod sursa(job #26127)

Utilizator victorsbVictor Rusu victorsb Data 5 martie 2007 11:24:25
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
#include <stdlib.h>

#define Nmax 100005

struct Trie
{
    Trie()
    {
        fs = fd = NULL;
        nod = 0;
    }
    
    int nod;
    Trie *fs, *fd;
};

const int hmax = 21;
int n, sol = -1, start, stop;
int sir[Nmax], sum[Nmax];
Trie *trie;

void citire()
{
    int i;
    scanf("%d\n", &n);
    for (i = 1; i <= n; ++i)
        scanf("%d ", &sir[i]);
}

void baga(int val, int pos)
{
    int i;
    Trie *cur = trie;
    
    for (i = 20; i >= 0; --i)
    {
        if ((val >> i) & 1)
        {
            if (cur -> fd == NULL)
                cur -> fd = new(Trie);
            cur = cur -> fd;
        }
        else
        {
            if (cur -> fs == NULL)
                cur -> fs = new(Trie);
            cur = cur -> fs;
        }
    }
    
    cur -> nod = pos;
}

int find(int val, int &pos)
{
    int i, ret = 0;
    Trie *cur = trie;
    
    for (i = 20; i >= 0; --i)
    {
        if ((val >> i) & 1)
        {
            if (cur -> fd != NULL)
            {
                cur = cur -> fd;
                ret += 1 << i;
            }
            else
                cur = cur -> fs;
        }
        else
        {
            if (cur -> fs != NULL)
                cur = cur -> fs;
            else
            {
                cur = cur -> fd;
                ret += 1 << i;
            }
        }
    }
    
    pos = cur -> nod;
    return ret;
}

void solve()
{
    int i, j, v, pos;

    trie = new(Trie);
    baga(0, 0);
    
    for (i = 2; i <= n; ++i)
        sir[i] ^= sir[i-1];
    
    for (i = 1; i <= n; ++i)
    {
        v = ~sir[i];
        v = find(v, pos);
        
        if (sir[i] ^ v > sol)
        {
            sol = v ^ sir[i];
            start = pos + 1;
            stop = i;
        }
        baga(sir[i], i);
    }
    printf("%d %d %d\n", sol, start, stop);
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    citire();
    solve();
    return 0;
}