Cod sursa(job #429882)

Utilizator laserbeamBalan Catalin laserbeam Data 30 martie 2010 16:16:34
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
// Catalin Balan
// Tue Mar 30 15:08:49 EEST 2010
// Infoarena - Xor Max

#include <cstdio>
#include <cstdlib>

using namespace std;

#define NMAX 100005
#define max(a,b) (a>b?a:b)

#define FIN "xormax.in"
#define FOUT "xormax.out"

// PARSARE
#define CHUNK 8192
char g_buf[CHUNK];
int g_p=CHUNK-1;

inline int get()
{

	int x = 0;
	while (g_buf[g_p] < '0' || g_buf[g_p] > '9')
		if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;

	while (g_buf[g_p] >= '0' && g_buf[g_p] <= '9')
	{
		x = x*10 + g_buf[g_p]-'0';
		if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;
	}
	return x;
}
// END PARSARE

struct tNod {
	int cine;
	tNod *kid[2];
};

tNod *root;

int n, nbiti;
int a[NMAX];

void addToTrie( int x, int j )
{
	tNod *p = root, *q;
	for ( int i = nbiti; i > 0; i>>=1)
	{
		int bit = ( (x&i) != 0);
		if ( !p->kid[bit] )
		{
			q = new tNod;
			q->cine = NULL;
			q->kid[0] = q->kid[1] = NULL;
			p->kid[bit] = q;
		}
		p = p->kid[bit];
	}
	p->cine = j;
}

int cauta( int x )
{
	tNod *p = root;
	for (int i = nbiti; i > 0; i>>=1)
	{
		int bit = ( (x&i) == 0 );
		if ( p->kid[bit] ) p = p->kid[bit];
		else p = p->kid[1-bit];
	}
	return p->cine;
}

int main(int argv, char ** argc)
{
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);

	n = get();
	a[0] = 0;
	int maxim = 0;
	for (int i = 1; i <= n; ++i)
	{
		int aux = get();
		a[i] = a[i-1]^aux;
		maxim = max(maxim, a[i]);
	}
	for (nbiti = 1; nbiti <= maxim; nbiti<<=1);
	nbiti>>=1;

	root = new tNod;
	root->cine = NULL;
	root->kid[0] = root->kid[1] = NULL;

	addToTrie(0,0);

	maxim = -1;
	int p1 = 0, p2 = 0;
	for (int i = 1; i <= n; ++i)
	{
		int care = cauta( a[i] );
		fprintf( stderr, "%d %d - %d %d = %d\n", i, a[i], care, a[care], a[i]^a[care] );
		if ( (a[i]^a[care]) > maxim )
		{
			maxim = a[i]^a[care];
			p1 = care+1;
			p2 = i;
		}
		addToTrie(a[i], i);
	}

	printf("%d %d %d\n", maxim, p1, p2);

	return EXIT_SUCCESS;
}