Cod sursa(job #733923)

Utilizator tiganu_dolarMancea Catalin tiganu_dolar Data 13 aprilie 2012 10:40:16
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>

#define MAXBIT 21
#define NMAX 100005

int val_xor[NMAX],n;
int best = -1,ind1,ind2;

struct trie
{
	int pozitie;
	trie *directie[2];
	trie() { directie[0] = directie[1] = 0; };
};

trie *radacina;

void insert(int val,int indice_bit, trie *nod, int poz)
{
	if(indice_bit < 0)
	{
		nod->pozitie = poz;
		return ;
	}	
	
	int bit = ((val & (1 << indice_bit)) == 0 ? 0 : 1);
	
	if(!nod->directie[bit])
		nod->directie[bit] = new trie();
	insert(val,indice_bit - 1, nod->directie[bit], poz);	
}

int find_poz(int val,int indice_bit,trie *nod)
{
	if(indice_bit < 0)
		return nod->pozitie;
		
	int bit = (val & (1 << indice_bit));
	bit = 1 - (!bit ? 0 : 1);	
	
	if(nod->directie[bit])
		return find_poz(val,indice_bit - 1, nod->directie[bit]);
		
	return find_poz(val, indice_bit - 1, nod->directie[!bit]);	
}

int main ()
{
	int i,val,poz;
	
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
	
	scanf("%d",&n);
	
	radacina = new trie();
	insert(0,MAXBIT,radacina,0);
	
	for(i = 1; i <= n; i++)
	{
		//printf("ok\n"); 	
		scanf("%d",&val);
		val_xor[i] = (val_xor[i - 1] ^ val);		

		poz = find_poz(val_xor[i], MAXBIT, radacina);
		//printf("mac\n");
		
		if((val_xor[poz] ^ val_xor[i]) > best)
		{
			best = val_xor[poz] ^ val_xor[i];
			ind1 = poz + 1;
			ind2 = i;
		}
		insert(val_xor[i], MAXBIT, radacina,i);
		//printf("bau\n");
	}	
	
	printf("%d %d %d\n",best,ind1,ind2);
	
	return 0;
}