Cod sursa(job #1626039)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 2 martie 2016 21:57:39
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie
{
    int xo,val;
    trie *st,*dr;
    trie()
    {
        xo=val=0;
        st=dr=0;
    }
};
trie *root=new trie;
void update(int pxor,int i)
{
    trie *nod=root;
    for(int i=21;i>=0;i--)
    {
        bool ok=pxor &(1<<i);
        if(ok==0)
        {
            if(nod->st==0) nod->st=new trie;
            nod=nod->st;
        }
        else
        {
            if(nod->dr==0) nod->dr=new trie;
            nod=nod->dr;
        }
    }
    nod->xo=pxor;
    nod->val=i;
}
int cauta(int pxor,int &pos)
{
    trie *nod=root;
    for(int i=21;i>=0;i--)
    {
        bool ok=pxor&(1<<i);
        if(ok==1&&nod->st!=0) nod=nod->st;
        else if(ok==1) nod=nod->dr;
        else if(ok==0&&nod->dr!=0) nod=nod->dr;
        else nod=nod->st;
    }
    pos=nod->val;
    return pxor^nod->xo;
}
int main()
{
    int result=-(1<<30),pxor=0,n,i,j,step,pos1=0,pos2=0,pos;
    update(pxor,0);
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>j;
        pxor^=j;
        update(pxor,i);
        step=cauta(pxor,pos);
        if(step>result)
        {
            result=step;
            pos1=pos;pos2=i;
        }
    }
    if(pos1==pos2+1) pos1=pos2;
    fout<<result<<" "<<pos1+1<<" "<<pos2;
}