Pagini recente » Cod sursa (job #612593) | Cod sursa (job #1312511) | Cod sursa (job #2520435) | Cod sursa (job #2704333) | Cod sursa (job #2618907)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, nr_max_biti, v[100100], xorpart[100100], sol_value = -1, sol_left, sol_right;
struct trie {
trie *bit[2];
vector<int> poz;
trie() {
poz.clear();
bit[0] = bit[1] = nullptr;
}
};
int calc_nr_max_biti(int x) {
int nr_biti = 0;
while (x) {
nr_biti++;
x >>= 1;
}
return max(1, nr_biti);
}
void add(trie *nod, int x, int nr_bit, int p) {
if (nr_bit == 0) {
nod->poz.push_back(p);
return;
}
for (int i = 0; i <= 1; i++) {
if (((x & (1 << (nr_bit - 1))) > 0) == (bool)i) {
/// bitul de pe pozitia "nr_bit - 1" este egal cu i (0 sau 1)
if (nod->bit[i] == nullptr)
nod->bit[i] = new trie();
add(nod->bit[i], x, nr_bit - 1, p);
}
}
}
vector<int> find_best_poz(trie *nod, int nr_bit, int want) {
if (nr_bit == 0)
return nod->poz;
bool want_bit = (bool)((want & (1 << (nr_bit - 1))) > 0);
if (nod->bit[want_bit] == nullptr)
return find_best_poz(nod->bit[!want_bit], nr_bit - 1, want);
return find_best_poz(nod->bit[want_bit], nr_bit - 1, want);
}
int main() {
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> v[i];
xorpart[i] = xorpart[i - 1] ^ v[i];
nr_max_biti = max(nr_max_biti, calc_nr_max_biti(v[i]));
}
trie *root = new trie();
add(root, 0, nr_max_biti, 0);
for (int i = 1; i <= n; i++)
add(root, xorpart[i], nr_max_biti, i);
for (int i = 1; i <= n; i++) {
vector<int> pozitii = find_best_poz(root, nr_max_biti, (xorpart[i] ^ ((1 << nr_max_biti) - 1)));
for (int left : pozitii) {
if (left >= i)
break;
int best_value = xorpart[i] ^ xorpart[left];
if (best_value > sol_value || best_value == sol_value && i == sol_right && left + 1 > sol_left) {
sol_value = best_value;
sol_left = left + 1;
sol_right = i;
}
}
}
fout << sol_value << ' ' << sol_left << ' ' << sol_right << '\n';
return 0;
}