Pagini recente » Cod sursa (job #1370783) | Cod sursa (job #2323020) | Cod sursa (job #2711200) | Cod sursa (job #2778116) | Cod sursa (job #2705589)
#include <bits/stdc++.h>
using namespace std;
#define input f
#define output g
ifstream f("xormax.in");
ofstream g("xormax.out");
struct Nod {
int next[2];
int index=-1;
Nod() {
next[0] = next[1] = -1;
}
};
vector<Nod> trie(1);
void insert(int x, int index) {
int v = 0;
for (int i = 20; i >= 0; i--) {
int bit = (x & (1 << i)) != 0;
if (trie[v].next[bit] == -1) {
trie[v].next[bit] = trie.size();
trie.emplace_back(Nod());
}
v = trie[v].next[bit];
}
trie[v].index = index;
}
vector<int> query(int x) {
vector<int> ans(2, 0);
int v = 0;
for (int i = 20; i >= 0 && v != -1; i--) {
int bit = (x & (1 << i)) != 0;
if (trie[v].next[1 - bit] != -1) {
v = trie[v].next[1 - bit];
ans[0] += (1 << i);
} else v = trie[v].next[bit];
}
if (v != -1)
ans[1] = trie[v].index;
return ans;
}
int main() {
int n, xor_sum = 0;
input >> n;
vector<int> ans(3, 0);
for (int i = 0, x; i < n; i++) {
input >> x;
xor_sum ^= x;
vector<int> current = query(xor_sum);
if (current[0] > ans[0])
ans[0] = current[0], ans[1] = current[1]+1, ans[2] = i;
if (xor_sum > ans[0])
ans[0] = xor_sum, ans[1] = 0, ans[2] = i;
insert(xor_sum, i);
}
output << ans[0] << ' ' << 1 + ans[1] << ' ' << 1 + ans[2];
return 0;
}