Cod sursa(job #977553)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 26 iulie 2013 08:43:47
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define maxb 21

using namespace std;

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

const int N = 100010;

int n, sol = -1, st, dr, start, sumxor[N];
struct Trie{
    int poz; Trie *f[2];
    Trie()
    {
        f[0] = f[1] = 0;
        poz = 0;
    }
};
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;
}