Pagini recente » Cod sursa (job #2842488) | Cod sursa (job #642043) | Cod sursa (job #989432) | Cod sursa (job #1553923) | Cod sursa (job #2823150)
#include <iostream>
#include <fstream>
using namespace std;
const int ROOT = 0;
const int NMAX = 1e5;
const int SIGMA = 2;
const int MAX_DEPTH = 21;
int bit_array[MAX_DEPTH];
int second_bit_array[MAX_DEPTH];
void get_bit ( int x ) {
for ( int index = MAX_DEPTH - 1; index; index -- ) {
bit_array[index] = x % 2;
x /= 2;
}
}
int get_number ( int bit[] ) {
int result = 0;
for ( int index = 0; index < MAX_DEPTH; index ++ )
result = result * 2 + bit[index];
return result;
}
void delete_array ( int bit[] ) {
for ( int i = 0; i < MAX_DEPTH; i ++ )
bit[i] = 0;
}
void debug_array ( int bit[] ) {
for ( int i = 0; i < MAX_DEPTH; i ++ )
cout << bit[i] << " ";
cout << "\n";
}
struct BIT_TRIE {
struct node {
int link[SIGMA];
int end_prefix;
} ds[1 + NMAX * MAX_DEPTH];
int index = 0;
void add_number ( int bit[], int pos ) {
int node = ROOT;
for ( int i = 0; i < MAX_DEPTH; i ++ ) {
if ( !ds[node].link[bit[i]] )
ds[node].link[bit[i]] = ++ index;
node = ds[node].link[bit[i]];
}
ds[node].end_prefix = pos;
}
int search_invers ( int bit[], int result[] ) {
int node = ROOT;
for ( int i = 0; i < MAX_DEPTH; i ++ ) {
if ( ds[node].link[1 - bit[i]] ) {
result[i] = 1 - bit[i];
node = ds[node].link[1 - bit[i]];
}
else {
result[i] = bit[i];
node = ds[node].link[bit[i]];
}
}
return ds[node].end_prefix;
}
} trie;
ifstream fin ( "xormax.in" );
ofstream fout ( "xormax.out" );
int main()
{
int pref_xor = 0, max_xor = 0;
int b, e;
int n; fin >> n;
for ( int i = 1; i <= n; i ++ ) {
get_bit ( pref_xor );
trie.add_number ( bit_array, i );
int x; fin >> x; pref_xor ^= x;
get_bit ( pref_xor ); delete_array ( second_bit_array );
///debug_array ( bit_array );
///debug_array ( second_bit_array );
int pos = trie.search_invers ( bit_array, second_bit_array );
///debug_array ( second_bit_array );
int best = get_number ( second_bit_array );
///cout << best;
best = pref_xor ^ best;
if ( best > max_xor ) {
max_xor = best;
b = pos, e = i;
}
}
fout << max_xor << " ";
fout << b << " " << e;
return 0;
}