Pagini recente » Cod sursa (job #47874) | Cod sursa (job #2007771) | Cod sursa (job #652933) | Monitorul de evaluare | Cod sursa (job #3347690)
#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, N_BITS = 25;
// deci stai
// daca o vreau pe cea mai scurta
// imi tin min sau max in trie?
// 50/50 garantat
struct binary_trie {
struct trie_node {
int children[2];
int cnt, idx;
explicit trie_node () {
children[0] = children[1] = -1;
cnt = 0;
idx = -oo; // de ce am pus inf aici?
}
};
vector<trie_node> tree;
explicit binary_trie () {
tree.emplace_back();
}
void insert (int v, int idx) {
int root = 0;
tree[root].cnt++;
tree[root].idx = max(tree[root].idx, idx); // sa fie primul idx
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 = max(tree[root].idx, idx); // sa fie primul idx
}
// tree[root].idx = min(tree[root].idx, idx); // sa fie primul 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) {
// okay deci aparent am stop minim intain
// si dupa secv cea mai scurta
// ... ok gng
if (i < r || (i == r && (i - idx) < (r - l + 1))) {
l = idx + 1;
r = i;
}
}
trie.insert(px[i], i);
}
cout << max_val << " " << l << " " << r << "\n";
return 0;
}