Cod sursa(job #1464769)

Utilizator rangerChihai Mihai ranger Data 24 iulie 2015 16:34:14
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
# include <bits/stdc++.h>
using namespace std;

ifstream fi("xormax.in");
ofstream fo("xormax.out");

struct trie{
     trie * a[2];
     trie () { a[0] = a[1] = NULL; }
};
trie * root = new trie();

void ins(int x)
{
    trie * p = new trie();
    p = root;
    for (int i=21;i>=0;i--){
        int bit= (1<<i) & x;  bit = bit != 0;
        if (!p->a[bit]) p->a[bit] = new trie();
        p = p->a[bit];
    }
}
int query(int x)
{
      trie * p = new trie();
    p = root;
    int ret = 0;
    for (int i=21;i>=0;i--){

        int bit = (1<<i) & x; bit = (bit != 0);
        bit ^= 1;

        if (p->a[bit])  ret=ret*2+1;
        else ret*=2,  bit^=1;
        p = p->a[bit];
    }
    return ret;
}

int n, a[100004],  x[100004], res, stop, start;
int main()
{
    fi>>n;
    for (int i=1;i<=n;i++)
    {
        fi >> a[i];
        x[i] = a[i];
        if (i == 1)
        {
            ins(x[i]); res=max(res,x[i]);
            continue;
        }
        x[i] ^= x[i-1];

        int can = query(x[i]);
        if (can > res)
        {
            res = can;
            stop = i;
        }
        ins(x[i]);
    }


    int sum = a[stop];
    int i;
    for ( i=stop-1; sum != res; i--) sum ^= a[i];
    start = i+1;
    fo << res << " " << start << " " << stop;
    return 0;
}