Pagini recente » Cod sursa (job #79074) | Cod sursa (job #1662482) | Cod sursa (job #935882) | Cod sursa (job #1588528) | Cod sursa (job #2837809)
#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;
}