Cod sursa(job #415764)

Utilizator DraStiKDragos Oprica DraStiK Data 11 martie 2010 20:14:49
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <algorithm>
using namespace std;

#define SIGMA 2

int n,sumaxor,indice,best,start,final;

struct trie
{
    trie *fiu[SIGMA];
    int poz;

    trie ()
    {
        poz=0;
        fiu[0]=fiu[1]=0;
    }
} *arb=new trie;

void insert (trie *nod, int level,int val,int poz)
{
    if (!level)
    {
        nod->poz=poz;
        return ;
    }
    --level;
    if (!nod->fiu[(val&(1<<level))>>level])
        nod->fiu[(val&(1<<level))>>level]=new trie;
    insert (nod->fiu[(val&(1<<level))>>level],level,val,poz);
}

int query (trie *nod,int level,int val)
{
    if (!level)
    {
        indice=nod->poz;
        return 0;
    }
    --level;
    if (nod->fiu[1^((val&(1<<level))>>level)])
        return ((1^((val&(1<<level))>>level))<<level)+query (nod->fiu[1^((val&(1<<level))>>level)],level,val);
    return (val&(1<<level))+query (nod->fiu[(val&(1<<level))>>level],level,val);
}

void solve ()
{
    int i,x,y;

    insert (arb,22,0,0);
    for (i=1; i<=n; ++i)
    {
        scanf ("%d",&x);
        sumaxor^=x;
        y=query (arb,22,sumaxor);
        if ((sumaxor^y)>best)
        {
            best=(sumaxor^y);
            start=indice+1;
            final=i;
        }
        insert (arb,22,sumaxor,i);
    }
    printf ("%d %d %d",best,start,final);
}

int main ()
{
    freopen ("xormax.in","r",stdin);
    freopen ("xormax.out","w",stdout);

    scanf ("%d",&n);
    solve ();

    return 0;
}