Cod sursa(job #46828)

Utilizator amadaeusLucian Boca amadaeus Data 3 aprilie 2007 00:26:59
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>

using namespace std;

#define NX 100010

struct node {
	int poz;
	node *l, *r;
	node() {
		poz = -1;
		l = r = NULL;
	}
};

typedef node* trie;

trie T;
int N, vmax, start, stop, s[ NX ];

void baga( trie T, int key, int p, int mask ) {
	T->poz = p;
	if( !mask )
		return;
	if( key & mask ) {
		if( T->r == NULL )
			T->r = new( node );
		baga( T->r, key, p, mask >> 1 );
	}
	else {
		if( T->l == NULL )
			T->l = new( node );
		baga( T->l, key, p, mask >> 1 );
	}
}

int find( trie T, int key, int mask ) {
	if( !mask )
		return T->poz;
	if( key & mask ) {
		if( T->l )
			return find( T->l, key, mask >> 1 );
		else
			return find( T->r, key, mask >> 1 );
	}
	else {
		if( T->r )
			return find( T->r, key, mask >> 1 );
		else
			return find( T->l, key, mask >> 1 );
	}
}

void cit() {
	int i, j, x, val;
	
	scanf( "%d", &N );

	T = new( node );
	baga( T, 0, 0, 1 << 20 );
	s[0] = 0;
	
	for( i = 1; i <= N; i++ ) {
		scanf( "%d", &x );
		s[i] = s[i-1] ^ x;
		j = find( T, s[i], 1 << 20 );
		val = s[i] ^ s[j];
		if( val > vmax ) {
			vmax = val;
			start = j+1;
			stop = i;
		}
		baga( T, s[i], i, 1 << 20 );
	}
}

void scr() {
	printf( "%d %d %d\n", vmax, start, stop );
}
		
int main() {
	freopen( "xormax.in", "r", stdin );
	freopen( "xormax.out", "w", stdout );

	cit();
	scr();

	return 0;
}