Pagini recente » Cod sursa (job #3307678) | Cod sursa (job #3349588) | Cod sursa (job #3347811) | Cod sursa (job #3307620) | Cod sursa (job #3318676)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int LOG = 20;
struct TRIE {
struct Node {
Node* sons[2];
Node() {
sons[0] = nullptr;
sons[1] = nullptr;
}
};
Node* radacina = nullptr;
void add(Node*& p, int x, int bit = LOG) {
if (p == nullptr) {
p = new Node();
}
if (bit < 0) {
return;
}
int b = (x & (1 << bit)) > 0;
add(p->sons[b], x, bit - 1);
}
int query(Node*& p, int x, int bit = LOG) {
if (p == nullptr) {
return 0;
}
if (bit < 0) {
return 0;
}
int b = (x & (1 << bit)) > 0;
int preferabil = 1 - b;
if (p->sons[preferabil]) {
return (1 << bit) + query(p->sons[preferabil], x, bit - 1);
} else {
return query(p->sons[1 - preferabil], x, bit - 1);
}
}
};
int main() {
int n;
fin >> n;
vector<int> prefix(n + 1, 0);
vector<int> v(n + 1);
TRIE trie;
trie.add(trie.radacina, 0);
int max_xor = -1;
int dr = -1;
int st = -1;
for (int i = 1; i <= n; i++) {
fin >> v[i];
prefix[i] = (prefix[i - 1] ^ v[i]);
int verif = trie.query(trie.radacina, prefix[i]);
if (verif > max_xor) {
max_xor = verif;
dr = i;
}
trie.add(trie.radacina, prefix[i]);
}
for (int i = 1; i <= dr; i++) {
if ((prefix[dr] ^ prefix[i - 1]) == max_xor) {
st = i;
}
}
fout << max_xor << ' ' << st << ' ' << dr << '\n';
return 0;
}