Pagini recente » Cod sursa (job #657535) | Cod sursa (job #1095201) | Cod sursa (job #664152) | Cod sursa (job #657480) | Cod sursa (job #3334740)
#include <bits/stdc++.h>
using namespace std;
struct Node{
Node* sons[2]{};
int count;
int endings;
int pos;
Node() {
sons[0] = sons[1] = nullptr;
count = 0;
endings = 0;
pos = 0;
}
};
void insert(Node* root, int nr, int idx) {
Node* current = root;
for(int i = 31; i >= 0; --i) {
int bit = nr >> i & 1;
++current->count;
if(current->sons[bit] == nullptr)
current->sons[bit] = new Node;
current = current->sons[bit];
}
current->pos = idx;
++current->endings;
}
int query(Node* root, int nr) {
Node* current = root;
for(int i = 31; i >= 0; --i) {
int bit = nr >> i & 1;
int flipped = bit ^ 1;
if(current->sons[flipped] == nullptr) {
current = current->sons[bit];
} else {
current = current->sons[flipped];
}
}
if(current->endings)
return current->pos;
return -1;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifndef LOCAL
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
#endif
Node* root = new Node;
insert(root, 0, 0);
int n, xormax = -1, st = 1, dr = 1; cin >> n;
vector<int> px(n+1);
cin >> px[1];
xormax = px[1];
insert(root, px[1], 1);
for(int i = 2; i <= n; ++i) {
cin >> px[i];
px[i] ^= px[i-1];
int j = query(root, px[i]);
insert(root, px[i], i);
if(j != -1) {
if((px[i] ^ px[j]) > xormax) {
xormax = px[i] ^ px[j];
st = j + 1;
dr = i;
}
}
}
cout << xormax << ' ' << st << ' ' << dr;
return 0;
}