Cod sursa(job #1195840)

Utilizator apopeid15Apopei Daniel apopeid15 Data 8 iunie 2014 11:17:50
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
 
using namespace std;
struct nod
{
    nod *F[2];
    int Start;
    nod()
    {
        F[0]=F[1]=NULL;
        Start=0;
    }
};
int n,SC,sol,sol_now,i,start,stop,b,dir,val,start_now;
nod *root,*p;
void insert(int);
int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    root=new nod;
    insert(0);
    SC=0;sol=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&val);
        SC^=val;sol_now=0;start_now=0;
        for(b=1<<20,p=root;;b>>=1)
        {
            if(!b){start_now=p->Start;break;}
            dir=b&SC?1:0;
            if(p->F[1-dir]!=NULL)
            {
                sol_now|=b;
                p=p->F[1-dir];
            }
 
                else p=p->F[dir];
        }
        if(sol<sol_now)
        {
            start=1+p->Start;
            stop=i;
            sol=sol_now;
        }
        insert(SC);
    }
    if(!sol)printf("0 1 1\n");
    else printf("%d %d %d\n",sol,start,stop);
    return 0;
}
void insert(int v)
{
    for(b=1<<20,p=root;b;b>>=1)
    {
        dir=b&v?1:0;
        if(!p->F[dir])p->F[dir]=new nod;
        p=p->F[dir];
        p->Start=i;
    }
 
}