Cod sursa(job #469626)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 8 iulie 2010 15:00:41
Problema Xor Max Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include<cstdio>
#include<vector>
#define N 1<<17
using namespace std;
vector<int> val[N];
int s,nrn,maxas,n,pi,pf,maxv,xorr[N],a[N];
int f[N][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].push_back(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)
        {
            int minl=N,pmin=0;
            for(vector<int>::iterator it=val[nod].begin();it!=val[nod].end();it++)
                if(poz>=*it && poz-*it+1<minl)
                    minl=poz-*it+1, pmin=*it;
            if((xorr[poz]^xorr[pmin])>maxv)
            {
                maxv=xorr[poz]^xorr[pmin];
                pi=pmin+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;
}