Cod sursa(job #1889194)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 22 februarie 2017 17:00:16
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#define BIT(x) (1<<(x))
#define bmax 20

using namespace std;

struct Trie
{
    Trie* f[2];
    int ind;
    Trie()
    {
        f[0] = f[1] = NULL;
    }
} r;

int val;
int rval, pval;
int best, ibest, sbest;

void update(Trie* t, int pos = bmax)
{
    t->ind = pval;
    if(pos < 0) return;
    if(val & BIT(pos))
    {
        if(t->f[1] == NULL)
            t->f[1] = new Trie();
        update(t->f[1], pos - 1);
    }
    else
    {
        if(t->f[0] == NULL)
            t->f[0] = new Trie();
        update(t->f[0], pos - 1);
    }
}

void query(Trie* t, int pos = bmax)
{
    if(pos < 0)
    {
        pval = t->ind;
        return;
    }
    if(val & BIT(pos))
    {
        if(t->f[0] != NULL)
        {
            rval |= BIT(pos);
            query(t->f[0], pos - 1);
        }
        else
        {
            query(t->f[1], pos - 1);
        }
    }
    else
    {
        if(t->f[1] != NULL)
        {
            rval |= BIT(pos);
            query(t->f[1], pos - 1);
        }
        else
        {
            query(t->f[0], pos - 1);
        }
    }
}

int main()
{
    int n;
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    val = 0;
    update(&r);
    scanf("%d", &n);
    int sum = 0, x;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        sum ^= x;
        val = sum;
        rval = 0;
        query(&r);
        if(rval > best)
        {
            best = rval;
            ibest = pval + 1;
            sbest = i;
        }
        val = sum;
        pval = i;
        update(&r);
    }
    printf("%d %d %d", best, ibest, sbest);
    return 0;
}