Pagini recente » Cod sursa (job #1283820) | Cod sursa (job #3353820) | Cod sursa (job #1554323) | Cod sursa (job #1623647) | Cod sursa (job #3345062)
#include <bits/stdc++.h>
#warning That's not NP, that's my NP!
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef pair<int, int> pii;
const int oo = numeric_limits<int>::max() / 2;
const int N = 1e5;
struct binary_trie {
struct trie_node {
int children[2];
int cnt, idx;
trie_node () {
children[0] = children[1] = -1;
cnt = 0;
idx = oo;
}
};
vector<trie_node> tree;
const int N_BITS = 21;
binary_trie () {
tree.emplace_back();
}
void insert (int v, int idx) {
int root = 0;
tree[root].cnt++;
for (int b = N_BITS; b >= 0; b--) {
int bv = (v >> b) & 1;
if (tree[root].children[bv] == -1) {
tree[root].children[bv] = tree.size();
tree.emplace_back(); // tre sa bag un copil nou
}
root = tree[root].children[bv];
tree[root].cnt++;
}
tree[root].idx = idx;
}
pii mx_xor (int v) {
int root = 0, mx = 0;
for (int b = N_BITS; b >= 0; b--) {
int bv = (v >> b) & 1;
if (tree[root].children[1 - bv] != -1) {
mx |= (1 << b);
root = tree[root].children[1 - bv];
} else {
root = tree[root].children[bv];
}
}
return make_pair(mx, tree[root].idx);
}
};
int x[N + 1], px[N + 1];
binary_trie trie;
signed main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n;
cin >> n;
int max_val = -oo, l = -1, r = -1;
trie.insert(0, 0);
for (int i = 1; i <= n; i++) {
cin >> x[i];
px[i] = px[i - 1] ^ x[i];
auto [val, idx] = trie.mx_xor(px[i]);
if (val > max_val) {
max_val = val;
l = idx + 1;
r = i;
} else if (val == max_val && (i - idx) < (r - l + 1)) {
l = idx + 1;
r = i;
}
trie.insert(px[i], i);
}
cout << max_val << " " << l << " " << r << "\n";
return 0;
}