Pagini recente » Cod sursa (job #520891) | Cod sursa (job #2932514) | Cod sursa (job #885200) | Cod sursa (job #2060855) | Cod sursa (job #2816773)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "xormax.in" );
ofstream fout( "xormax.out" );
const int BIT = 20;
const int SIGMA = 2;
const int NMAX = 1e5;
int ans, pos;
struct Node {
int pos;
vector <Node*> v;
Node() : v(SIGMA, nullptr) {}
};
struct Trie {
private :
Node* root_ = nullptr;
Node* insert_(int number, int bit, Node* node);
int query_(int number, int bit, Node* node);
public:
void insert(int number, int bit) { root_ = insert_(number, bit, root_); }
int query(int number, int bit) { return query_(number, bit, root_); }
};
int v[NMAX + 2];
Node* Trie::insert_ (int number, int bit, Node* node) {
if( node == nullptr )
node = new Node();
if( bit > -1 ) {
int mbit = number & (1 << bit);
mbit = mbit > 0 ? 1 : 0;
node->v[mbit] = insert_(number, bit - 1, node->v[mbit]);
}
else if( bit == -1 )
node->pos = pos;
return node;
}
int Trie::query_ (int number, int bit, Node* node) {
if( bit == -1 ) {
ans = node->pos;
return 0;
}
int mbit = number & (1 << bit);
mbit = mbit > 0 ? 1 : 0;
mbit ^= 1;
if( node->v[mbit] == nullptr )
mbit ^= 1;
return (mbit * (1 << bit)) + query_(number, bit - 1, node->v[mbit]);
}
int main() {
Trie trie;
int n, xorr, i, rasp, maxx, start, stop;
fin >> n;
for( i = 1; i <= n; ++i )
fin >> v[i];
trie.insert(0, 20);
maxx = xorr = 0;
for( i = 1; i <= n; ++i ) {
xorr ^= v[i];
ans = 0;
rasp = trie.query(xorr, 20);
if( maxx < (xorr ^ rasp) ) {
maxx = xorr ^ rasp;
start = 1 + ans;
stop = i;
}
pos = i;
trie.insert(xorr, 20);
}
fout << maxx << " " << start << " " << stop;
return 0;
}