Cod sursa(job #945281)

Utilizator assa98Andrei Stanciu assa98 Data 1 mai 2013 16:28:54
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
using namespace std;

struct Trie
{
    int poz;
    Trie *b[2];

    Trie()
    {
        poz=0;
        b[0]=b[1]=NULL;
    }
} *T=new Trie;

void add(const int x,int bit,Trie *T,const int poz)
{
    if(bit==-1)
    {
        T->poz=poz;
        return;
    }

    int a=x&(1<<bit);
    a=(a>0);

    if(T->b[a]==NULL)
        T->b[a]=new Trie;

    add(x,bit-1,T->b[a],poz);
}

int best_poz(const int x,int bit,Trie *T)
{
    if(bit==-1)
        return T->poz;

    int a=x&(1<<bit);
    a=(a>0);

    if(T->b[1-a]!=NULL)
        return best_poz(x,bit-1,T->b[1-a]);
    return best_poz(x,bit-1,T->b[a]);
}

int xmax=-1;
int start,stop;

int n;
int v[100100];

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    add(0,20,T,0);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        v[i]=v[i]^v[i-1];
        int j=best_poz(v[i],20,T);
        if((v[i]^v[j])>xmax)
        {
            start=j+1;
            stop=i;
            xmax=v[i]^v[j];
        }
        add(v[i],20,T,i);
    }
    printf("%d %d %d",xmax,start,stop);
    return 0;
}