Cod sursa(job #73014)

Utilizator peanutzAndrei Homorodean peanutz Data 16 iulie 2007 11:02:28
Problema Xor Max Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#define BITMAX 25

struct tri
{
	int list;
	struct tri *st, *dr;
};
typedef struct tri *trie;
trie t;


int crt;
int x;
int n;
int max, begin, end;
int poz;

void make(int nr, trie t)
{
	if(nr < 0)
		return;

	if((crt & (1<<nr)) > 0)
	{
		if(t -> st != NULL)
		{
			poz = t -> list;
			make(nr-1, t -> st);
		}
		else if(t -> dr != NULL)
		{
			poz = t -> list;
			x |= (1<<nr);
			make(nr-1, t -> dr);
		}
		else
		{
			x = crt;
			return;
		}
	}
	else
	{
		if(t -> dr != NULL)
		{
			poz = t -> list;
			x |= (1<<nr);
			make(nr-1, t -> dr);
		}
		else if(t -> st != NULL)
		{
			poz = t -> list;
			make(nr-1, t -> st);
		}
		else
		{
			x = crt;
			return;
		}
	}
}

void update(trie t, int nr, int poz)
{
	if(nr < 0)
		return;

	t -> list = poz;
	if((crt & (1<<nr)) > 0)
	{
		if(!(t -> dr))
		{
			t -> dr = new tri;
			(t -> dr) -> st = (t -> dr) -> dr = NULL;
		}

		update(t -> dr, nr-1, poz);
	}
	else
	{
		if(!(t -> st))
		{
			t -> st = new tri;
			(t -> st) -> st = (t -> st) -> dr = NULL;
		}

		update(t -> st, nr-1, poz);
	}
}
//int past[100], h;

int main()
{
	int i, a;
	freopen("xormax.in", "r", stdin);
	freopen("xormax.out", "w", stdout);

	scanf("%d", &n);
	t = new tri;
	t -> st = t -> dr = NULL;


	scanf("%d", &crt);
	max = crt;
	begin = end = 1;

	for(i = 2; i <= n; ++i)
	{
		scanf("%d", &a);

		if(a > max)
			max = a, begin = i, end = i;

		crt ^= a;

		if(crt > max)
			max = crt, begin = i, end = i;

		poz = i;
		x = 0;

		make(BITMAX, t);

		if( (crt ^ x) > max)
			max = (crt ^ x), begin = poz, end = i;

		update(t, BITMAX, i);

		//past[++h] = crt;
	}
	printf("%d ", max);

	if(begin == end)
		printf("%d %d\n", begin, end);
	else
		printf("%d %d\n", begin+1, end);


	return 0;
}