Pagini recente » Cod sursa (job #778960) | Cod sursa (job #3146585)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
using ll = long long;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int v[NMAX + 1];
struct Node {
int val;
int pos;
Node* leftChild;
Node* rightChild;
Node() {
val = pos = 0;
leftChild = rightChild = nullptr;
}
~Node() {
delete leftChild;
delete rightChild;
}
};
void insert(Node* root, int val, int pos) {
int bit;
for (bit = 20; bit >= 0; bit--) {
if( (val & (1 << bit)) != 0 ) {
if( root->rightChild != nullptr )
root = root->rightChild;
else {
root->rightChild = new Node();
root = root->rightChild;
}
}
else {
if( root->leftChild != nullptr )
root = root->leftChild;
else {
root->leftChild = new Node();
root = root->leftChild;
}
}
}
root->val = val;
root->pos = pos;
}
Node* query(Node* root, int xorr) {
int bit;
for( bit = 20; bit >= 0; bit-- ) {
int val = xorr & ( 1 << bit );
val ^= 1;
if( root->leftChild != nullptr || root->rightChild != nullptr ) {
if( ( val == 0 && root->leftChild != nullptr ) || root->rightChild == nullptr )
root = root->leftChild;
else
root = root->rightChild;
}
}
return root;
}
void solve() {
int n, i, xorr, ans, left, right;
fin >> n;
Node* root = new Node();
Node* aux = nullptr;
for (i = 0; i < n; i++) {
fin >> v[i];
}
insert(root, 0, 0);
xorr = 0;
ans = left = right = 0;
for (i = 0; i < n; i++) {
xorr = xorr ^ v[i];
aux = query(root, xorr);
if( (aux->val ^ xorr) > ans ) {
ans = aux->val ^ xorr;
left = aux->pos + 1;
right = i + 1;
}
insert(root, xorr, i + 1);
}
fout << ans << " " << left << " " << right;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}