Cod sursa(job #1311046)

Utilizator heracleRadu Muntean heracle Data 7 ianuarie 2015 17:37:53
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 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)
    {
        if(p->nrstop>trans)
            p->nrstop=trans;
        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);
    }

    for(int i=0; i<=n; i++)
    {
        trans=i;
        add(start, v[i],20);
    }

    int rez=0;

    int a,b;

    int act;

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

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

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

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

    return 0;
}