Cod sursa(job #149881)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 6 martie 2008 10:50:16
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#define biti 21
long i,j,n,a,x[100001],zero,b,bit,
max,start,stop,maxc,startc,stopc,poz0,poz1,poz,arb[4200000];
int main()
{
	FILE *f=fopen("xormax.in","r"),*g=fopen("xormax.out","w");
        fscanf(f,"%ld",&n);
	for(i=1;i<=n;i++){fscanf(f,"%ld",&a);x[i]=x[i-1]^a;}
	zero=(1<<biti);max=x[1];start=1;stop=1;
	for(i=1;i<=n;i++)
	{ maxc=x[i];startc=i;stopc=i;
	  poz=1;
	  for(b=biti-1;b>=0;b--)
	  { bit=(1<<b)&x[i];
	    if(bit)
	     {  poz1=poz<<1;
		if(!arb[poz1])poz1++;
		poz=poz1;
	     }
	    else
	     { poz1=(poz<<1)|1;
	       if(!arb[poz1])poz1--;
	       poz=poz1;
	     }
	  }
	  if(poz!=poz0){j=arb[poz];maxc=x[i]^x[j];startc=j;}
	  if(maxc>max){start=startc;stop=stopc;max=maxc;}
	  poz0=poz=zero+x[i];
	  do{arb[poz]=i;poz/=2;}while(poz);
	}
	fprintf(g,"%ld %ld %ld\n",max,start,stop);
	fcloseall();
	return 0;
}