Cod sursa(job #392798)

Utilizator KrillKnossisKuchiki Byakuya KrillKnossis Data 8 februarie 2010 12:34:22
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 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;
}