Cod sursa(job #986915)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 19 august 2013 18:47:08
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>
int max,start,stop,poz;
int apar[2100000];
struct nod{
    nod *fi[2];
    nod(){
        fi[0]=fi[1]=0;
    }
};
void add(nod *p,int x,int pas){
    if(pas==-1)
        return;
    int xx=((x&(1<<pas))!=0);
    if(pas==0 && p->fi[xx]==0)
        apar[x]=poz;
    if(pas==0 && p->fi[xx])
        apar[x]=poz;
    if(p->fi[xx]==0)
        p->fi[xx]=new nod();
    add(p->fi[xx],x,pas-1);
}
int caut(nod *p,int x,int pas){
    if(pas==-1)
        return 0;
    int xx=((x&(1<<pas))!=0);
    if(xx==0){
        if(p->fi[1])
            return caut(p->fi[1],x,pas-1)+(1<<pas);
        else
            return caut(p->fi[0],x,pas-1);
    }
    else{
        if(p->fi[0])
            return caut(p->fi[0],x,pas-1);
        else
            return caut(p->fi[1],x,pas-1)+(1<<pas);
    }
}
int main(){
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n,xr=0,a=0,aa;
    nod *tr=new nod();
    scanf("%d",&n);
    for(poz=0;poz<n;++poz){
        scanf("%d",&aa);
        xr=xr^aa;
        if(poz)
            a=caut(tr,xr,20);
        add(tr,xr,20);
        if((xr^a)>max){
            max=(xr^a);
            start=apar[a]+1;
            stop=poz;
        }
    }
    printf("%d %d %d\n",max,start+1,stop+1);
    fclose(stdin);
    fclose(stdout);
    return 0;
}