Cod sursa(job #365556)

Utilizator ilincaSorescu Ilinca ilinca Data 19 noiembrie 2009 09:59:56
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h> 

#define nmax 100005
#define B 21

struct Trie
{
	int k;
	Trie *fiu [2];
	
	Trie ()
	{
		k=0;
		fiu [0]=fiu [1]=0;
	}
};

int r=-1, w, n, p, first, last, v [nmax], xp [nmax];
Trie *t=new Trie;

void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=1; i <= n; ++i)
	{	
		scanf ("%d", &v [i]);
		xp [i]=xp [i-1]^v [i];
	}
}

void add (Trie *k, int b)
{
	if (b == -1)
	{
		k->k=p;
		return;
	}
	int cv=w & (1 << b);
	if (cv)
	       cv=1;
	if (k->fiu [cv] == 0)
		k->fiu [cv]=new Trie;
	add (k->fiu [cv], b-1);
}

int cauta (Trie *k, int b)
{
	if (b == -1)
	       return k->k;
	int cv=w & (1 << b);
	if (cv)
		cv=1;
	if ((k->fiu [cv]) == 0) 
	{
		if (cv == 0) 
			cv=1;
		else
			cv=0;
	}
	if (k->fiu [cv] == 0) 
		return 0;
	return cauta (k->fiu [cv], b-1);	
}

void rez ()
{
	int i, k;
	w=0;
	p=0;
	add (t, 21);
	for (i=1; i <= n; ++i)
	{
		w= ~xp [i];
		k=cauta (t, 21);
		fprintf(stderr, "%d %d %d %d\n", i, xp [i], w, k); 
		if (r < (xp [i]^xp [k])) 
		{
			r=xp [i]^xp [k];
			first=k+1;
			last=i;
		}
		w=xp [i];
		p=i;
		add (t, 21);
	}	
}

int main ()
{
	freopen ("xormax.in", "r", stdin);
	freopen ("xormax.out", "w", stdout);
	scan ();
	rez ();
	printf ("%d %d %d\n", r, first, last);
	return 0;
}