Cod sursa(job #3345440)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 9 martie 2026 17:24:26
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
using namespace std;
struct trie{
	int poz = 0;
	trie* v[2] = { nullptr, nullptr };
};
trie *root = new trie;
int v[100005];
static void modif( trie *nod, int x, int poz, int layer ){
	int fiu;
	if( layer == -1 ){
		nod->poz = poz;
		return;
	}
	if( ( x & ( 1 << layer ) ) == 0 ){
		fiu = 0;
	}
	else{
		fiu = 1;
	}
	if( nod->v[fiu] == nullptr ){
		nod->v[fiu] = new trie;
	}
	modif( nod->v[fiu], x, poz, layer - 1 );
}
static int sum( trie *nod, int x, int layer ){
	int fiu;
	if( layer == -1 ){
		return nod->poz;
	}
	if( ( x & ( 1 << layer ) ) == 0 ){
		fiu = 1;
	}
	else{
		fiu = 0;
	}
	if( nod->v[fiu] != nullptr ){
		return sum( nod->v[fiu], x, layer - 1 );
	}
	return sum( nod->v[1 - fiu], x, layer - 1 );
}
int main(){
	int n, i, j, max_xor, r_i, r_j;
	ifstream fin( "xormax.in" );
	ofstream fout( "xormax.out" );
	fin >> n;
	max_xor = r_i = r_j = -1;
	modif( root, 0, 0, 21 );
	for( i = 1; i <= n; i++ ){
		fin >> v[i];
		v[i] = ( v[i] ^ v[i - 1] );
		j = sum( root, v[i], 21 );
		if( ( v[i] ^ v[j] ) > max_xor ){
			max_xor = ( v[i] ^ v[j] );
			r_i = i;
			r_j = j;
		}
		modif( root, v[i], i, 21 );
	}
	fout << max_xor << ' ' << r_j + 1 << ' ' << r_i;
	return 0;
}