Cod sursa(job #3358931)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 22 iunie 2026 09:50:49
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
// 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;
}