Cod sursa(job #3354626)

Utilizator GabrielaTudoracheTudorache Gabriela GabrielaTudorache Data 19 mai 2026 14:19:43
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#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;
}