Cod sursa(job #87660)

Utilizator devilkindSavin Tiberiu devilkind Data 28 septembrie 2007 14:07:59
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <stdio.h>
#include <string.h>
#define NMAX 100002

long int TR[NMAX*22][2],i,j,k,n,v[NMAX],poz[NMAX],FIN[NMAX],sol[3],p,nst,len;
long int cv[NMAX];

void query()
{
long int nod,bit,sum,s,x,y,i;
sum=0;
for (nod=0,i=len;i;i--)
        {
        bit=cv[len-i];
        if (FIN[nod]) {
                      s=sum^k;
                      x=poz[nod]+1;y=p;
                      if (s>sol[0]) {sol[0]=s;sol[1]=x;sol[2]=y;}
                      if ((s==sol[0])&&(y<sol[2])) {sol[1]=x;sol[2]=y;}
                      if ((s==sol[0])&&(y==sol[2])&&(x>sol[1])) sol[1]=x;
                      }                      
        if (TR[nod][!bit]) {        
                           nod=TR[nod][!bit];
                           if (!bit==1) sum=sum+ (1 << i);
                           }
                else if (TR[nod][bit])  {
                                        nod=TR[nod][bit];
                                        if (bit==1) sum=sum+ (1 << (len - i -1));
                                        }
                        else break;
        }
}

void baga_trie()
{

long int nod=0,i;

for (i=len;i;i--)
        {
        if (!TR[nod][ cv[i] ]) TR[nod][ cv[i] ]=++nst;

        nod=TR[nod][ cv[i] ];
        
        if (i==1) {FIN[nod]=1;poz[nod]=p;}
        }

}


int main()
{

freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);

scanf("%ld",&n);

for (i=1;i<=n;i++)
        {
        scanf("%ld",&k);
        v[i]=v[i-1]^k;
        }

for (i=1;i<=n;i++)
        {
        for (k=v[i],j=1;k;k/=2,j++);
        if (j-1>len) len=j-1;
        }
len++;
FIN[0]=1;nst=0;

for (i=1;i<=n;i++)
        {
        memset(cv,0,sizeof(cv));
        k=v[i];
        p=i;
        for (j=1;k;k/=2,j++) cv[j]=k%2;
        k=v[i];
        baga_trie();
        query();
        }
printf("%ld %ld %ld",sol[0],sol[1],sol[2]);
return 0;
}