Cod sursa(job #692889)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 26 februarie 2012 20:36:32
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <algorithm>

#define lim 22
#define MAX 100050

using namespace std;

int v[MAX], sumaXOR[MAX], maxim, start, end, n;

struct Trie
{
    int inf;
    Trie *st, *dr;
    Trie()
    {
        inf = 0;
        st = dr = 0;
    }
}*T = new Trie;

void add(Trie *nod, int poz, int x)
{
    int i, bit;
    for(i = lim; i >= 0; i--)
    {
        bit = (x & (1 << i));
        if(bit)
        {
            if(!nod->st)
                nod->st = new Trie;
            nod = nod->st;
        }
        else
        {
            if(!nod->dr)
                nod->dr = new Trie;
            nod = nod->dr;
        }
    }
    nod->inf = poz;
}

int lookAfter(Trie *nod, int x)
{
    int i, bit;
    for(i = lim; i >= 0; i--)
    {
        bit = (x & (1 << i));
        if(bit)
        {
            if(nod->dr)
                nod = nod->dr;
            else
                nod = nod->st;
        }
        else
        {
            if(nod->st)
                nod = nod->st;
            else
                nod = nod->dr;
        }
    }
    return nod->inf;
}

int main()
{
    int i,j;
    ifstream fin("xormax.in");
    fin>>n;
    add(T, 0, 0);
    for(i=1; i<=n; i++)
    {
        fin>>v[i];
        sumaXOR[i]=(sumaXOR[i-1]^v[i]);
        j=lookAfter(T,sumaXOR[i]);
        if(maxim<(sumaXOR[j]^sumaXOR[i]))
        {
            maxim=(sumaXOR[j]^sumaXOR[i]);
            start = j;
            end = i;
        }
        add(T,i, sumaXOR[i]);
    }
    fin.close();
    ofstream fout("xormax.out");
    fout<<maxim<<' '<<(start+1)<<' '<<end<<"\n";
    fout.close();
    return 0;
}