Cod sursa(job #1312008)

Utilizator heracleRadu Muntean heracle Data 8 ianuarie 2015 20:06:37
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>

FILE* in=fopen("xormax.in","r");
FILE* out=fopen("xormax.out","w");

const int Q=100002;
int n;

int v[Q];

struct Nod{
    Nod *t[2];
    int nrstop;
    Nod()
    {
        t[0]=t[1]=NULL;
        nrstop=100007;
    }
};

Nod *start=new Nod;

int trans;


int ask(Nod *p,int x,int lvl)
{
    if(lvl==-1)
    {
        trans=p->nrstop;
        return 0;
    }

    bool bit=(x&(1<<lvl));

    if(p->t[!bit] !=NULL )
    {
        return (1<<lvl) + ask(p->t[!bit],x,lvl-1);
    }
    return ask(p->t[bit],x,lvl-1);
}

Nod *add(Nod *p, int x, int lvl)
{
    if(p==NULL)
    {
        p=new Nod;
    }
    if(lvl==-1)
    {
        p->nrstop=trans;
        return p;
    }

    bool bit=(x&(1<<lvl));

    p->t[bit]=add(p->t[bit],x,lvl-1);

    return p;
}

int main()
{
    fscanf(in,"%d",&n);

    int x;

    for(int i=1; i<=n; i++)
    {
        fscanf(in,"%d",&x);
        v[i]=(v[i-1]^x);
    }

    int rez=0;

    int a,b;

    int act;

    trans=0;
    add(start,0,21);

    for(int i=1; i<=n; i++)
    {
        act=ask(start,v[i],21);

        if(act>rez)
        {
            rez=act;
            a=trans;
            b=i;
        }

        trans=i;
        add(start,v[i],21);
    }

    fprintf(out,"%d %d %d",rez,a+1,b);

    return 0;
}