Cod sursa(job #81100)

Utilizator sealTudose Vlad seal Data 31 august 2007 13:54:06
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>
#define Nm 100001
#define Logm 20
#define bit ((v&1<<p)!=0)
int F[1<<Logm+1][2],A[Nm],n,k;
int xormax,start,finish;

void read()
{
    int i;

    freopen("xormax.in","r",stdin);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",A+i);
}

void insert(int n, int v, int p)
{
    if(!F[n][bit])
        F[n][bit]=++k;
    if(p)
        insert(F[n][bit],v,p-1);
}

int ans;

void find_max(int n, int v, int p)
{
    if(F[n][bit^1])
    {
        ans|=(bit^1)<<p;
        if(p)
            find_max(F[n][bit^1],v,p-1);
    }
    else
    {
        ans|=bit<<p;
        if(p)
            find_max(F[n][bit],v,p-1);
    }
}

void solve()
{
    int X[Nm],i;

    X[0]=0; xormax=-1;
    insert(0,0,Logm);
    for(i=1;i<=n;++i)
    {
        X[i]=X[i-1]^A[i];
        ans=0; find_max(0,X[i],Logm);
        if((ans^X[i])>xormax)
        {
            xormax=ans^X[i];
            finish=i;
        }
        insert(0,X[i],Logm);
    }

    for(i=0;i<finish;++i)
        if((X[i]^X[finish])==xormax)
            start=i+1;
}

void write()
{
    freopen("xormax.out","w",stdout);
    printf("%d %d %d\n",xormax,start,finish);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}