Cod sursa(job #312604)

Utilizator galacticaBattlestar galactica Data 6 mai 2009 16:50:14
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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;
}