Cod sursa(job #1001544)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 25 septembrie 2013 13:41:47
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>

#define maxn 100001

using namespace std;

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

int n,maxv=-1,start,stop,secvstop,secvval,sum;
int v[maxn];

struct trie_node
{
    int stop;
    trie_node *s[2];
    trie_node ()
    {
        s[0]=0;
        s[1]=0;
        stop=0;
    }
}*trie;

void trie_insert (int nr, int st, int i, trie_node *current)
{
    if (i==-1)
    {
        current->stop = st;
        return;
    }

    int which = ((nr>>i)&1);

    if (current->s[which]==0)
        current->s[which] = new trie_node;

    trie_insert (nr,st,i-1,current->s[which]);
}

void trie_search (int nr, int i, trie_node *current)
{
    if (i==-1)
    {
        secvstop = current->stop;
        return;
    }

    int which = 1 - ((nr>>i)&1);

    if (current->s[which]==0) which = 1 - which;

    secvval += (which<<i);
    trie_search (nr,i-1,current->s[which]);
}

int main()
{
    fin>>n;

    for (int i=1; i<=n; ++i)
    {
        fin>>v[i];
    }

    trie = new trie_node;
    trie_insert (0,0,20,trie);
    sum=0;

    for (int i=1; i<=n; ++i)
    {
        sum ^= v[i];

        secvval = 0; secvstop=0;

        trie_search (sum,20,trie);

        if ((secvval^sum) > maxv)
        {
            maxv = (secvval^sum);
            start = secvstop+1;
            stop = i;
        }

        trie_insert (sum,i,20,trie);
    }

    fout<<maxv<<" "<<start<<" "<<stop<<" ";
}