Cod sursa(job #469630)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 8 iulie 2010 15:04:16
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include<cstdio>
#define N 1<<17
#define M 1<<20
int val[M];
int s,nrn,maxas,n,pi,pf,maxv,xorr[N],a[N];
int f[M][2];
int check(int x,int put)
{
    if(x&put)
        return 1;
    return 0;
}
void insert(int nod,int nb,int put,int poz)
{
    if(put==1<<21)
    {
        val[nod]=poz;
        return;
    }
    if(f[nod][check(nb,put)])
    {
        insert(f[nod][check(nb,put)],nb,put*2,poz);
        return;
    }
    f[nod][check(nb,put)]=++nrn;
    insert(nrn,nb,put*2,poz);
}
void search(int nod,int nb,int put,int asem)
{
    if(put==1<<21)
    {
        if(asem>maxas)
            maxas=asem;
        return;
    }
    for(int i=0;i<2;i++)
        if(f[nod][i])
        {
            if(i==(check(nb,put)))
            {
                search(f[nod][i],nb,put*2,asem+1);
                continue;
            }
            search(f[nod][i],nb,put*2,asem);
        }
}
void solve(int nod,int nb,int put,int poz,int asem)
{
    if(put==1<<21)
    {
        if(asem==maxas)
        {
            if((xorr[poz]^xorr[val[nod]])>maxv && val[nod]<poz)
            {
                maxv=xorr[poz]^xorr[val[nod]];
                pi=val[nod]+1;
                pf=poz;
            }
        }
        return;
    }
    for(int i=0;i<2;i++)
        if(f[nod][i])
        {
            if(i==(check(nb,put)))
            {
                solve(f[nod][i],nb,put*2,poz,asem+1);
                continue;
            }
            solve(f[nod][i],nb,put*2,poz,asem);
        }
}
int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    s=a[1];
    xorr[1]=s;
    nrn=1;
    insert(1,s,1<<0,1);
    for(int i=2;i<=n;i++)
    {
        s^=a[i];
        xorr[i]=s;
        insert(1,s,1<<0,i);
    }
    s=a[1];
    pi=1;
    pf=1;
    maxv=0;
    for(int i=2;i<=n;i++)
    {
        s=s^a[i];
        int sp=0;
        for(int j=0;j<=20;j++)
            if(!(s&(1<<j)))
                sp+=(1<<j);
        maxas=0;
        search(1,sp,1<<0,0);
        solve(1,sp,1<<0,i,0);
    }
    printf("%d %d %d",maxv,pi,pf);
    return 0;
}