Pagini recente » Cod sursa (job #952820) | Monitorul de evaluare | Cod sursa (job #61453) | Cod sursa (job #3345240) | Cod sursa (job #3345440)
#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;
}