Cod sursa(job #360638)

Utilizator freak93Adrian Budau freak93 Data 1 noiembrie 2009 13:30:43
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<fstream>

using namespace std;

const char iname[]="xormax.in";
const char oname[]="xormax.out";
const int maxn=100005;

ifstream f(iname);
ofstream g(oname);

int a[maxn],i,j,n,x[maxn],maxt,u,v;

struct trie
{
    trie *l;
    trie *r;
    int p;
    trie()
    {
        l=r=0;
    }
} *root= new trie;

void insert(trie *k,int v,int p)
{
    int step=(1<<22);
    trie *i=k;
    for(;step;step>>=1)
    {
        i->p=p;
        if(v&step)
        {
            if(!i->l)
                i->l=new trie;
            i=i->l;
            continue;
        }
        if(!(i->r))
            i->r=new trie;
        i=i->r;
    }
    i->p=p;
}

int getp(trie *k,int v)
{
    int step=(1<<22);
    trie *i=k;
    for(;step;step>>=1)
    {
        if((v&step&&i->r)||!i->l)
        {
            i=i->r;
            continue;
        }
        i=i->l;
    }

    return i->p;
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i],x[i]=x[i-1]^a[i];

    insert(root,0,0);
    maxt=-0x3f3f3f3f;
    for(i=1;i<=n;++i)
    {
        j=getp(root,x[i]);
        if((x[i]^x[j])>maxt)
            maxt=x[i]^x[j],u=j+1,v=i;
        insert(root,x[i],i);
    }

    g<<maxt<<" "<<u<<" "<<v<<"\n";

    f.close();
    g.close();

    return 0;
}