Cod sursa(job #45785)

Utilizator amadaeusLucian Boca amadaeus Data 1 aprilie 2007 21:46:40
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>

using namespace std;

#define NX 100001
#define BX 3

#define left(X) ((X)<<1)
#define right(X) (((X)<<1) + 1)

int s[ NX ], res, N, start, stop;
int A[ 1<<(BX+1) + 1 ];

void baga( int key, int poz ) {
	int mask, node;

	for( node = 1, mask = 1 << (BX-1); mask; mask >>= 1 ) {
		node = ( mask & key ) ? right(node) : left( node );
		A[ node ] = poz;
	}
}

int xmax( int key ) {
	int mask, node;

	for( node = 1, mask = 1 << (BX-1); mask > 1; mask >>= 1 )
		node = ( mask & key ) ? left( node ) : right( node );

	return A[ node ];
}

void cit() {
	int i, j, x, val;
	
	scanf( "%d", &N );
	for( i = 1; i <= N; i++ ) {
		scanf( "%d", &x );
		s[i] = s[i-1] ^ x;
		j = xmax( s[i] );
		val = s[i] ^ s[j];
		if( res < val ) {
			res = val;
			stop = i;
			start = j+1;
		}
		baga( s[i], i );
	}
}

void scr() {
	printf( "%d %d %d\n", res, start, stop );
}

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

	cit();
	scr();

	return 0;
}