Cod sursa(job #717968)

Utilizator danalex97Dan H Alexandru danalex97 Data 20 martie 2012 12:52:27
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>

using namespace std;

struct str
{
    int a;
    bool b;
};

str d[4194304];
int v[100001],n;

void update(int nod,int l,int r)
{
    if (r==-1)
    {
        d[nod].a=l;
        d[nod].b=1;
        return;
    }
    if (v[l]&(1<<r))
        update((nod<<1)+1,l,r-1);
    else
        update(nod<<1,l,r-1);
    d[nod].b=d[nod<<1].b|d[(nod<<1)+1].b;
}

int query(int nod,int l,int r)
{
    if (r==-1)
        return d[nod].a;
    else if (((l&(1<<r))&&d[nod<<1].b==1)||d[(nod<<1)+1].b==0)
        return query(nod<<1,l,r-1);
    else
        return query((nod<<1)+1,l,r-1);

}

int main()
{
    int i,sol=-1,l=0,r=0,p;
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d\n",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d",&v[i]);
        v[i]^=v[i-1];
    }
    update(1,0,20);
    for (i=1;i<=n;++i)
    {
        p=query(1,v[i],20);
        if (sol<(v[i]^v[p]))
        {
            sol=v[i]^v[p];
            l=p+1,r=i;
        }
        update(1,i,20);
    }
    printf("%d %d %d\n",sol,l,r);
    return 0;
}