Cod sursa(job #1520834)

Utilizator ipus1Stefan Enescu ipus1 Data 9 noiembrie 2015 16:17:44
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<cstdio>
#define pow2 1048576
int vc[10000000],v[100010],nr;
char vec[25];
int pow(int k)
    {int x=1,i;
    for(i=1;i<=k;i++)
        x*=2;
    return x;
    }
struct trie
    {trie *fii[3];
    trie()
        {for (int i=0;i<=2;i++)
            fii[i]=NULL;
        }
    };
trie *T=new trie;
void insert(trie *nod,char *s)
    {if(*s==NULL)
        return ;
    if(nod->fii[*s]==NULL)
        nod->fii[*s]=new trie;
    insert(nod->fii[*s],s+1);
    }
int xoreala(trie *nod,char *s,int a)
    {if(*s==NULL)
        return 0;
    if(nod->fii[*s]==NULL)
        {if(vec[20-a]==2)
            return xoreala(nod->fii[1],s+1,a-1);
        else
            {nr+=pow(a);
            return xoreala(nod->fii[0],s+1,a-1);
            }
        }
    else
        {if(vec[20-a]==2)
            nr+=pow(a);
        return pow(a)+xoreala(nod->fii[*s],s+1,a-1);
        }
    }
int main ()
{freopen ("xormax.in","r",stdin);
freopen ("xormax.out","w",stdout);
int n,max=0,start,stop,i,j,x,y,z,p;
scanf("%d",&n);
scanf("%d",&x);
v[1]=x;
x=pow2;
y=v[1];
for(j=20;j>=0;j--)
    {if(y>=x)
        {vec[20-j]=2;
        y-=x;
        }
    else
        vec[20-j]=1;
    x/=2;
    }
insert(T,vec);
max=v[1];
start=stop=1;
vc[v[1]]=1;
for(i=2;i<=n;i++)
    {scanf("%d",&x);
    for(j=0;j<=20;j++)
        vec[j]=1;
    v[i]=(x^v[i-1]);
    vc[v[i]]=i;
    p=pow2;
    y=v[i];
    for(j=20;j>=0;j--)
        {if(y<p)
            vec[20-j]=2;
        else
            y-=p;
        p/=2;
        }
    nr=0;
    z=xoreala(T,vec,20);
    if(z>max)
        {max=z;
        stop=i;
        start=vc[nr]+1;
        }
    for(j=0;j<=20;j++)
        vec[j]=1;
    x=pow2;
    y=v[i];
    for(j=20;j>=0;j--)
        {if(y>=x)
            {vec[20-j]=2;
            y-=x;
            }
        else
            vec[20-j]=1;
        x/=2;
        }
    insert(T,vec);
    }
printf("%d %d %d",max,start,stop);
return 0;
}