Cod sursa(job #182498)

Utilizator tm_raduToma Radu tm_radu Data 20 aprilie 2008 22:54:12
Problema Xor Max Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#define NM 100001

int n, a[NM], x[NM];
int p[] = {0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304};
int i, j, jmax, k, b, xmax, imax, pow;
typedef struct trie {
	int id;
	trie* c[2];
} TRIE, *PTRIE;
PTRIE root = new TRIE;

void Insert(trie* nod, int i, int pos);
int Query(trie* nod, int pos);

int main()
{
	freopen("xormax.in", "r", stdin);
	freopen("xormax.out", "w", stdout);
	scanf("%d", &n);
	root->c[0] = root->c[1] = 0;
	for ( i = 1; i <= n; i++ )
	{
		scanf("%d", &a[i]), x[i] = x[i-1] ^ a[i];
		j = 0, pow = 1;
		while ( x[i] >= pow ) j++, pow *= 2;
		if ( x[i] == 0 ) j = 1;
		b = b > j ? b : j;
	}
	// Build trie
	Insert(root, 1, b);
	xmax = x[1], imax = jmax = 1;
	// Solve
	for ( i = 2; i <= n; i++ )
	{
		// Solve for i
		if ( xmax < x[i] ) xmax = x[i], imax = i, jmax = 1;
		j = Query(root, b);
		if ( xmax < (x[i]^x[j]) ) xmax = x[i]^x[j], imax = i, jmax = j+1;
		// Insert i
		Insert(root, i, b);
	}

	printf("%d %d %d\n", xmax, jmax, imax);
	return 0;
}

void Insert(trie* nod, int i, int pos)
{
	if ( pos == 0 ) return;
	int bit = (x[i] & p[pos]) == 0 ? 0 : 1;
	if ( nod->c[bit] )
		Insert(nod->c[bit], i, pos-1);
	else
	{
		trie* q = new trie;
		q->id = i;
		q->c[0] = q->c[1] = 0;
		nod->c[bit] = q;
		Insert(q, i, pos-1);
	}
}

int Query(trie* nod, int pos)
{
	if ( pos == 0 ) return nod->id;
	int bit = (x[i] & p[pos]) == 0 ? 1 : 0;
	if ( nod->c[bit] )
		return Query(nod->c[bit], pos-1);
	else
		return Query(nod->c[1-bit], pos-1);
}