Cod sursa(job #945132)

Utilizator dariusdariusMarian Darius dariusdarius Data 30 aprilie 2013 16:36:25
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int sp[100005];
int bits(int x)
{
    int b;
    for(b=1;(1<<b)<=x;b++);
    return b-1;
}
struct Trie
{
    int ind;
    Trie *f[2];
    Trie()
    {
        ind=-1;
        memset(f,0,sizeof(f));
    }
} *root;
void add_node(Trie *T,int x,int b,int i)
{
    if(b<0)
    {
        T->ind=i;
        return;
    }
    T->ind=-1;
    int son=((x&(1<<b))!=0);
    if(T->f[son]==NULL)
        T->f[son]=new Trie();
    add_node(T->f[son],x,b-1,i);
}
int find_node(Trie *T,int x,int b)
{
    if(b<0)
        return T->ind;
    else
    {
        int son=((x&(1<<b))!=0);
        if(T->f[1-son]!=NULL)
            return find_node(T->f[1-son],x,b-1);
        else
            return find_node(T->f[son],x,b-1);
    }
}
int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n,a,maxb=0,ans=-1,ii,jj;
    scanf("%d",&n);
    root=new Trie();
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        sp[i]=sp[i-1]^a;
        maxb=max(maxb,bits(a));
    }
    add_node(root,0,maxb,0);
    for(int i=1;i<=n;i++)
    {
        int j=find_node(root,sp[i],maxb);
        if((sp[i]^sp[j])>ans)
            ans=sp[i]^sp[j],
            ii=j+1,
            jj=i;
        add_node(root,sp[i],maxb,i);
    }
    printf("%d %d %d",ans,ii,jj);
    return 0;
}