Pagini recente » Cod sursa (job #1297615) | Cod sursa (job #1810072) | Cod sursa (job #71237) | Cod sursa (job #2679084) | Cod sursa (job #2838091)
#include <bits/stdc++.h>
using namespace std;
const int PMAX = 20;
struct trie {
int i;
trie* bits[2];
};
trie* root = new trie();
void add( trie* root, int x, int p, int i ) {
if ( p == -1 ) {
root->i = i;
return;
}
if ( !(root->bits[(int)(x>>p)] != NULL) )
root->bits[(int)(x>>p)] = new trie();
add( root->bits[(int)(x>>p)], x & ( ( 1 << p ) - 1 ), p - 1, i );
}
pair <int, int> srch( trie* root, int x, int p, int ans ) {
if ( p == -1 ) return { ans, root->i };
if ( root->bits[1 - (x>>p)] == NULL ) return srch( root->bits[ (int)(x>>p)], x & ( ( 1 << p ) - 1 ), p - 1, ans * 2 + 0 );
if ( root->bits[1 - (x>>p)] != NULL ) return srch( root->bits[1-(int)(x>>p)], x & ( ( 1 << p ) - 1 ), p - 1, ans * 2 + 1 );
}
int main() {
ifstream fin( "xormax.in" );
ofstream fout( "xormax.out" );
int n, x = 0, i, a, l, r, maxim = 0;
fin >> n;
add( root, 0, PMAX, 0 );
for ( i = 1; i <= n; i ++ ) {
fin >> a;
x ^= a;
pair <int, int> aux = srch( root, x, PMAX, 0 );
if ( aux.first > maxim ) {
l = aux.second;
r = i;
maxim = aux.first;
}
add( root, x, PMAX, i );
}
fout << maxim << ' ' << l + 1 << ' ' << r;
return 0;
}