Cod sursa(job #589840)

Utilizator iepurasu_pasteGeorge Macovei iepurasu_paste Data 13 mai 2011 22:59:17
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>

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

int sol,rez=-1,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=0,y=0;
    
    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(s[i],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;
}