Cod sursa(job #2837809)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 22 ianuarie 2022 17:01:22
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>

int trie[ ( 1 << 22 ) ];
int x[ 100010 ];
bool bit[ 22 ];
int n;

int main()
{
	int maxx = -10, left, right;

	right  = ( 1 << 21 );
	for( int i = 0; i < right; i++ )
		trie[ i ] = -1;

	for( int i = 0; i < 22; i++ )
		trie[ ( 1 << i ) ] = 0;

	FILE *fin = fopen( "xormax.in", "r" );
	fscanf( fin, "%d", &n );
	for( int i = 1; i <= n; i++ ) {
		fscanf( fin, "%d", &x[ i ] );

		x[ i ] ^= x[ i - 1 ];
		for( int j = 0; j < 21; j++ )
			bit[ j ] = ( bool )( x[ i ] & ( 1 << ( 20 - j ) ) );

		int poz = 1;
		for( int j = 0; j < 21; j++ )
			if( trie[ ( ( poz << 1 ) + !bit[ j ] ) ] > 0 )
				poz = ( poz << 1 ) + !bit[ j ];
			else poz = ( poz << 1 ) + bit[ j ];
		
		poz = trie[ poz ];
		//printf( "%d -> %d\n", i, poz );
		if( ( x[ i ] ^ x[ poz ] ) > maxx ) {
			maxx = ( x[ i ] ^ x[ poz ] );
			left = poz + 1;
			right = i;
		}

		poz = 1;
		for( int j = 0; j < 21; j++ )
			trie[ ( poz = ( poz << 1 ) + bit[ j ] ) ] = i;
	}
	fclose( fin );

	FILE *fout = fopen( "xormax.out", "w" );
	fprintf( fout, "%d %d %d\n", maxx, left, right );
 	fclose( fout );
 	return 0;
}