Cod sursa(job #375299)

Utilizator freak93Adrian Budau freak93 Data 20 decembrie 2009 09:30:36
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

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

char s[1024];
int p=1023;
void cit(int &x)
{ while(s[p]<'0'||s[p]>'9') { ++p;
                              if(p==1024) fread(s,1,1024,stdin),p=0;
                              }
  x=0;
  while(s[p]>='0'&&s[p]<='9') { x=(x<<3)+(x<<1)+s[p]-'0';
                                ++p;
                                if(p==1024) fread(s,1,1024,stdin),p=0;
                                }
}

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()
{
    cit(n);
    for(i=1;i<=n;++i)
        cit(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);
    }

    printf("%d %d %d\n",maxt,u,v);

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

    return 0;
}