Pagini recente » Cod sursa (job #1639126) | Cod sursa (job #1913868) | Cod sursa (job #2208677) | Cod sursa (job #572331) | Cod sursa (job #2578275)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct Triple {
int x, y, z;
Triple(int x = 0, int y = 0, int z = 0) :
x(x), y(y), z(z) { }
inline bool operator<(const Triple& t) const {
return x < t.x || (x == t.x && (z > t.z || (z == t.z && y < t.y)));
}
};
class Trie {
private:
struct Node {
int pos = 0;
int next[2] = {-1, -1};
};
vector<Node> trie{1};
public:
void insert(int pos, int val) {
int node = 0;
for (int bit = 21; bit >= 0; bit--) {
bool now = (val & (1 << bit));
if (trie[node].next[now] == -1) {
trie[node].next[now] = trie.size();
trie.emplace_back();
}
node = trie[node].next[now];
}
trie[node].pos = pos;
}
Triple query(int pos, int val) {
int node = 0, ans = 0;
for (int bit = 21; bit >= 0; bit--) {
bool now = (val & (1 << bit));
if (trie[node].next[!now] == -1)
node = trie[node].next[now];
else {
node = trie[node].next[!now];
ans |= (1 << bit);
}
}
return Triple(ans, trie[node].pos + 1, pos);
}
};
int main() {
Trie trie; trie.insert(0, 0);
int n; fin >> n; Triple ans;
for (int i = 1, sum = 0; i <= n; i++) {
int x; fin >> x;
ans = max(ans, trie.query(i, x));
trie.insert(i, sum ^= x);
}
fout << ans.x << ' ' << ans.y << ' ' << ans.z << '\n';
fout.close();
return 0;
}