Cod sursa(job #929409)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 27 martie 2013 00:15:15
Problema Xor Max Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<algorithm>
#include<cstdio>
#include<vector>
#define BMax 22
#define NMax 100005
using namespace std;

int result,v[NMax],i,stg;
struct nod { int poz,v[3]; } blank;
vector<nod> T;

void add (int nr, int nod, int poz)
{
    if (poz==(BMax+1))
        T[nod].poz=max(T[nod].poz,i);
    else
    {
        int bit=((nr&(1<<(BMax-poz)))>0),next_nod;
        next_nod=T[nod].v[bit];
        if (!next_nod)
            next_nod=T.size(), T.push_back(blank);
        T[nod].v[bit]=next_nod;
        add(nr,next_nod,poz+1);
    }
}

void query (int nr, int nod, int poz)
{
    if (poz==BMax+1)
        stg=T[nod].poz;
    else
    {
        if (T[nod].v[0] && ((nr&(1<<(BMax-poz))) || !T[nod].v[1]))
            query(nr,T[nod].v[0],poz+1);
        else
        {
            result|=(1<<(BMax-poz));
            query(nr,T[nod].v[1],poz+1);
        }
    }
}

int main ()
{
    int sol=0,n,st,dr;
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    T.push_back(blank);
    T.push_back(blank);
    for (i=1; i<=n; i++)
    {
        scanf("%d",&v[i]);
        v[i]^=v[i-1];
    }
    add(0,1,0);
    for (i=1; i<=n; i++)
    {
        result=0;
        query(v[i],1,0);
        if ((result^v[i])>sol)
            sol=(result^v[i]), st=stg+1, dr=i;
        add(v[i],1,0);
    }
    printf("%d %d %d\n",sol,st,dr);
    return 0;
}