Cod sursa(job #604397)

Utilizator crushackPopescu Silviu crushack Data 22 iulie 2011 11:18:48
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#define NMax 100010

const char IN[]="xormax.in",OUT[]="xormax.out";

struct nod{
	int x;
	nod *next[2];
	nod(){
		x=0;next[0]=next[1]=NULL;
	}
} *first=new nod;

int N,Rez,A,B,ret;
int a[NMax];

void add(int x,int poz)
{
	int i=21;
	nod *node=first;
	while (i--)
	{
		int p= x & (1<<i) ? 1 : 0;
		if (!node->next[p])
			node->next[p]=new nod;
		node=node->next[p];
		node->x=poz;
	}
}

int query(int x)
{
	int i=21;
	nod *node=first;
	ret=0;
	
	while (i--)
	{
		int p= x & (1<<i) ? 1 : 0;
		p=!p;
		if (node->next[p]) node=node->next[p],ret+=(1<<i);
		else node=node->next[!p];
	}
	return node->x;
}

int main()
{
	int i,sum;
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	for (i=1;i<=N;++i) scanf("%d",a+i);
	fclose(stdin);
	
	add(0,0);A=1;B=1;Rez=a[1];
	for (i=1,sum=0;i<=N;++i)
	{
		sum^= a[i];
		int poz=query(sum);
		add(sum,i);
		
		if (ret>Rez) Rez=ret,A=poz+1,B=i;
	}
	
	freopen(OUT,"w",stdout);
	printf("%d %d %d\n",Rez,A,B);
	fclose(stdout);
	return 0;
}