Pagini recente » Cod sursa (job #1462620) | Statistici Raicu Alexandru (The20alex00) | Cod sursa (job #1462618) | Statistici Jalba Cristian (J_Cristian) | Cod sursa (job #3358931)
// https://infoarena.ro/problema/xormax
// trie binar pe prefixele xor
// xor pe (i..j) = pref[j] ^ pref[i-1]; pentru fiecare j cautam in trie pref-ul care maximizeaza
// fiecare nod retine indicele maxim stocat => la valoare egala iese secventa cea mai scurta
// iteram j (stop) crescator si actualizam doar la valoare strict mai mare => stop minim
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int MAXN = 100001;
const int BITS = 21; // valorile sunt < 2^21
const int MAXNODES = MAXN * (BITS + 1);
int pref[MAXN];
int ch[MAXNODES][2];
int maxIdx[MAXNODES];
int cnt = 0;
void insert(int val, int idx) {
int p = 0;
for (int b = BITS - 1; b >= 0; b--) {
int bit = (val >> b) & 1;
if (!ch[p][bit]) {
ch[p][bit] = ++cnt;
maxIdx[cnt] = -1;
}
p = ch[p][bit];
if (maxIdx[p] < idx) maxIdx[p] = idx;
}
}
int query(int val) {
int p = 0;
for (int b = BITS - 1; b >= 0; b--) {
int bit = (val >> b) & 1;
int want = bit ^ 1;
if (ch[p][want]) p = ch[p][want];
else p = ch[p][bit];
}
return maxIdx[p];
}
int main() {
int n;
fin >> n;
pref[0] = 0;
for (int i = 1; i <= n; i++) {
int x;
fin >> x;
pref[i] = pref[i - 1] ^ x;
}
insert(pref[0], 0);
int bestVal = -1, bestStart = 0, bestStop = 0;
for (int j = 1; j <= n; j++) {
int idx = query(pref[j]);
int val = pref[j] ^ pref[idx];
if (val > bestVal) {
bestVal = val;
bestStart = idx + 1; // i = (i-1) + 1, indexat de la 1
bestStop = j;
}
insert(pref[j], j);
}
fout << bestVal << ' ' << bestStart << ' ' << bestStop << '\n';
return 0;
}