Cod sursa(job #977557)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 26 iulie 2013 08:58:22
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

const int N = 100010;
const int maxb = 21;

int n, sol = -1, st, dr, start, sumxor[N];
struct Trie{
    int poz; Trie *f[2];
    Trie(){memset(f, 0, sizeof f);}
}; Trie* t = new Trie;

void Add(int val, int poz)
{
    Trie* x = t; bool bit;
    for(int i=maxb; i>=0; i--)
    {
        bit = ((1 << i) & val);
        if(!x->f[bit]) x->f[bit] = new Trie;
        x = x->f[bit];
    }
    x->poz = poz;
}

int Find(int val)
{
    Trie* x = t; bool bit;
    for(int i=maxb; i>=0; i--)
    {
        bit = ((1 << i) & val);
        if(x->f[!bit])
            x = x->f[!bit];
        else
            x = x->f[bit];
    }
    return x->poz;
}

int main()
{
    fin>>n;
    Add(0, 0);
    for(int i=1; i<=n; i++)
    {
        int x; fin>>x;
        sumxor[i] = (sumxor[i-1]^x);
        start = Find(sumxor[i]);
        Add(sumxor[i], i);
        if(sol < (sumxor[start] ^ sumxor[i]))
        {
            sol = sumxor[start] ^ sumxor[i];
            st = start + 1; dr = i;
        }
    }
    fout<<sol<<' '<<st<<' '<<dr;
    return 0;
}