Cod sursa(job #1462238)

Utilizator delia_99Delia Draghici delia_99 Data 17 iulie 2015 14:46:29
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>

using namespace std;
int n,x,i,sol=-1,p1,p2,xor1,val,xor2,pos;

struct Trie
{
    int p;
    Trie *fii[4];
    Trie()
    {
        p=0;
        fii[0]=NULL;
        fii[1]=NULL;
    }
};

Trie *T;

inline void upd(Trie *T,int q,int nr)
{
    int bit;
    if(nr==-1)
    {
        T->p=i;
        return;
    }
    bit=(q>>nr)&1;
    if(T->fii[bit]==NULL)
        T->fii[bit]=new Trie;
    upd(T->fii[bit],q,nr-1);
}

inline int query(Trie *T,int xor1,int nr)
{
    int bit;
    if(nr==-1)
        return T->p;
    bit=(xor1>>nr)&1;
    if(T->fii[bit^1]!=NULL)
    {
        xor2|=(1<<nr);
        query(T->fii[bit^1],xor1,nr-1);
    }
    else
        query(T->fii[bit],xor1,nr-1);
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);

    T=new Trie;
    upd(T,0,20);
    scanf("%d\n",&n);
    for(i=1; i<=n; ++i)
    {
        scanf("%d",&x);
        xor1^=x;
        xor2=0;
        pos=query(T,xor1,20);
        if(xor2>sol)
        {
            sol=xor2;
            p1=pos+1;
            if(pos==0)
                p1=i;
            p2=i;
        }
        upd(T,xor1,20);
    }
    printf("%d %d %d\n",sol,p1,p2);
    return 0;
}