Pagini recente » Diferente pentru problema/timbre intre reviziile 3 si 2 | Cod sursa (job #983687) | Cod sursa (job #3319979) | Borderou de evaluare (job #1320961) | Cod sursa (job #3333857)
#include <bits/stdc++.h>
using namespace std;
struct Node{
int sons[2];
int count;
int endings;
int pos;
};
vector<Node> trie;
Node newnode() {
Node node = {};
node.sons[0] = node.sons[1] = -1;
node.count = 0;
node.endings = 0;
node.pos = 0;
return node;
}
void insert(int nr, int idx) {
int current_pos = 0;
for(int i = 22; i >= 0; --i) {
int bit = nr >> i & 1;
++trie[current_pos].count;
if(trie[current_pos].sons[bit] == -1) {
trie.push_back(newnode());
trie[current_pos].sons[bit] = trie.size() - 1;
}
current_pos = trie[current_pos].sons[bit];
}
trie[current_pos].pos = idx;
++trie[current_pos].endings;
}
int query(int nr) {
int current_pos = 0;
for(int i = 22; i >= 0; --i) {
int bit = nr >> i & 1;
int flipped = bit ^ 1;
if(trie[current_pos].sons[flipped] == -1) {
current_pos = trie[current_pos].sons[bit];
} else {
current_pos = trie[current_pos].sons[flipped];
}
}
if(trie[current_pos].endings)
return trie[current_pos].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
int n, xormax = -1, st = -1, dr = -1; cin >> n;
vector<int> px(n);
cin >> px[0];
xormax = px[0];
trie.push_back(newnode());
insert(px[1], 0);
for(int i = 1; i < n; ++i) {
cin >> px[i];
px[i] ^= px[i-1];
insert(px[i], i);
int j = query(px[i]);
if(j != 1) {
if((px[i] ^ px[j]) > xormax) {
xormax = px[i] ^ px[j];
st = j + 2;
dr = i + 1;
}
}
}
cout << xormax << ' ' << st << ' ' << dr;
return 0;
}