Pagini recente » Cod sursa (job #1828053) | Cod sursa (job #1368535) | Cod sursa (job #3351572) | Cod sursa (job #2832078) | Cod sursa (job #3354626)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
// valori < 2^21, deci avem nevoie de 21 biti
const int BITS = 20;
const int MAXNOD = 21 * 100005;
int copii[MAXNOD][2], max_idx[MAXNOD], nr_nod = 1;
void insereaza(int val, int idx) {
int curr = 0;
for (int b = BITS; b >= 0; b--) {
int bit = (val >> b) & 1;
if (!copii[curr][bit]) {
copii[curr][bit] = nr_nod++;
}
curr = copii[curr][bit];
// retinem cel mai mare indice care a trecut prin nodul asta
max_idx[curr] = max(max_idx[curr], idx);
}
}
// returneaza {xor_maxim, indicele p* cu prefix[p*] XOR val maxim si p* maxim}
pair<int, int> query(int val) {
int curr = 0, rez = 0;
for (int b = BITS; b >= 0; b--) {
int bit = (val >> b) & 1;
int dorit = 1 - bit;
if (copii[curr][dorit]) {
curr = copii[curr][dorit];
rez |= (1 << b);
} else {
curr = copii[curr][bit];
}
}
return {rez, max_idx[curr]};
}
int main() {
int n;
fin >> n;
insereaza(0, 0);
int pref = 0, best_xor = 0, best_start = 1, best_stop = 1;
for (int j = 1; j <= n; j++) {
int x;
fin >> x;
pref ^= x;
// cautam p* in {0, ..., j-1} care maximizeaza pref XOR prefix[p*]
auto [xr, p] = query(pref);
if (xr > best_xor) {
best_xor = xr;
best_start = p + 1;
best_stop = j;
}
insereaza(pref, j);
}
fout << best_xor << " " << best_start << " " << best_stop;
}