Cod sursa(job #523651)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 18 ianuarie 2011 19:37:21
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>

#define maxim(a,b) ((a)>(b) ? (a) : (b))
#define MAXBIT 20

int sol,rez,n,s[100005];

struct nod {
    int poz;
    nod *dir[2];
    nod() { dir[0]=dir[1]=0; }
};
nod *rad;

void insert(int val, int k, nod* r, int pi)
{
    if (k<0)
    {
        r->poz=pi;
        return;
    }
    int bit=(val&(1<<k))!=0;
    
    if (r->dir[bit]==0)
        r->dir[bit]=new nod();
    insert(val, k-1, r->dir[bit], pi);
}

int find(int val,int k,nod* r)
{
    if(k<0)
        return r->poz;
        
    int bit=1-((val&(1<<k))!=0);
    if(r->dir[bit]==0)
        return find(val,k-1,r->dir[!bit]);
    return find(val,k-1,r->dir[bit]);
}

int main ()
{
    int i,val,poz,x,y;
    
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    
    rad=new nod();
    insert(0,MAXBIT,rad,0);
    
    for(i=1;i<=n;i++)
    {
        scanf("%d",&val);
        s[i]=s[i-1]^val;

        sol=s[poz=find(val,MAXBIT,rad)];
        if (rez < (sol^s[i]))
        {
            rez=(sol^s[i]);
            x=poz+1;
            y=i;
        }
        
        insert(s[i],MAXBIT,rad,i);
    }

    printf("%d %d %d\n",rez,x,y);
    return 0;
}