Cod sursa(job #1830016)

Utilizator antanaAntonia Boca antana Data 15 decembrie 2016 23:15:48
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
#include <cstring>

#define MAXN 100001
#define MAXS 23

struct trie{
    trie *son[2];
    int ind;

    trie(){
        son[1] = son[0] = 0;
        ind = 0;
    }
}*root;

int s[MAXS], v[MAXN], pos, xors[MAXN];

void add_trie(trie *aux, int *p)
{
    if(*p == -1)
    {
        aux->ind = pos;
        return;
    }

    if(aux->son[*p] == NULL)
        aux->son[*p] = new trie;

    add_trie(aux->son[*p], p+1);
}

int biggest_xor(trie *aux, int *p)
{
    if(*p == -1)
        return aux->ind;

    if(*p == 0 && aux->son[1] != NULL)
        return biggest_xor(aux->son[1], p+1);
    else if(*p == 0) return biggest_xor(aux->son[0], p+1);

    if(*p == 1 && aux->son[0] != NULL)
        return biggest_xor(aux->son[0], p+1);
    else if(*p == 1) return biggest_xor(aux->son[1], p+1);
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

    root = new trie;

    int k, byte, n, i, myxor, maxl = 1, maxr = 1, maxe = -1, j, left, x;

    scanf("%d%d", &n, &v[1]);

    myxor = 0;
    xors[1] = v[1];
    for(i=2; i<=n; ++i)
    {
        scanf("%d", &v[i]);
        if(v[i] > maxe)
            maxe = v[i];
    }

    byte = 20;
    while(!(maxe & (1<<byte)) && byte > 0) byte--;

    s[byte+1] = -1;
    add_trie(root, s);

    for(i=1; i<=n; ++i)
    {
        xors[i] = xors[i-1] ^ v[i];

        k = 0;
        for(j = byte; j>=0; --j)
            if(xors[i] & (1<<j))
                s[k++] = 1;
            else s[k++] = 0;

        s[k] = -1;
        left = biggest_xor(root, s);
        x = xors[i] ^ xors[left];

        if(x > myxor)
        {
            myxor = x;
            maxl = left+1;
            maxr = i;
        }

        pos = i;
        add_trie(root, s);
    }

    printf("%d %d %d", myxor, maxl, maxr);

    return 0;
}