Cod sursa(job #343162)

Utilizator radu_cppRadu Voroneanu radu_cpp Data 25 august 2009 10:52:18
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#define MAXLOG 22

struct nod{
	nod *a[2]; 
	int b[2];
};

nod *start;
int l[30],st,dr,n,i,max,poz,rasp,y,x;

void nou(nod *&p)
{
	p=new nod;
	p->a[1]=NULL;
	p->a[0]=NULL;
}
void trans(int x)
{
	int t;
	for (t=1; t<=MAXLOG; t++, x>>=1)
		l[t]=x&1;
}

void caut()
{
	nod *p;
	int t;
	p=start; rasp=0; poz=0;
	for (t=MAXLOG; t>0; t--)
		if (p->a[l[t] ^ 1]!=NULL){
			rasp=(rasp<<1)+(l[t]^1);
			poz=p->b[l[t]^1];
			p=p->a[l[t]^1];
		}
		else{
			rasp=(rasp<<1)+l[t];
			poz=p->b[l[t]];
			p=p->a[l[t]];
		}
}

void update(int poz)
{
	nod *p;
	int t;
	p=start;
	for (t=MAXLOG; t>0; t--){
		if (p->a[l[t]]==NULL)
			nou(p->a[l[t]]);
		p->b[l[t]]=poz;
		p=p->a[l[t]];
	}
}

int main()
{
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
	scanf("%d %d",&n,&x);
	nou(start);
	max=x; st=1; dr=1;
	trans(x); y=x;
	update(1);
	for (i=2; i<=n; i++){
		scanf("%d",&x);
		y^=x;
		trans(y);
		caut();
		if ((rasp ^ y) > max){
			max=rasp^y;
			st=poz;
			dr=i;
		}
		update(i);
	}
	if (st==dr) st--;
	printf("%d %d %d\n",max,st+1,dr);
	return 0;
}