Cod sursa(job #3353616)

Utilizator iLaurianLaurian Iacob iLaurian Data 8 mai 2026 17:02:12
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>

using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

const int MAX_BITS = 21;
const int MAX_NODES = 2200005;

int trie[MAX_NODES][2];
int prefix_index[MAX_NODES];
int nodeCount = 0;

void insert_trie(int value, int idx) {
    int u = 0;
    for (int i = MAX_BITS; i >= 0; i--) {
        int bit = (value >> i) & 1;
        if (trie[u][bit] == 0) {
            trie[u][bit] = ++nodeCount;
        }
        u = trie[u][bit];
    }
    prefix_index[u] = idx;
}

int query_trie(int value) {
    int u = 0;
    for (int i = MAX_BITS; i >= 0; i--) {
        int bit = (value >> i) & 1;
        int opposite_bit = 1 - bit;

        if (trie[u][opposite_bit] != 0) {
            u = trie[u][opposite_bit];
        } else {
            u = trie[u][bit];
        }
    }
    return prefix_index[u];
}

int P[100005];

int main() {
    int n;
    f >> n;

    int max_xor = -1;
    int best_start = -1, best_stop = -1;

    insert_trie(0, 0);
    P[0] = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        f >> x;
        P[i] = P[i - 1] ^ x;

        int prev_idx = query_trie(P[i]);
        int current_xor = P[i] ^ P[prev_idx];

        if (current_xor > max_xor) {
            max_xor = current_xor;
            best_start = prev_idx + 1;
            best_stop = i;
        }

        insert_trie(P[i], i);
    }

    g << max_xor << " " << best_start << " " << best_stop << "\n";

    return 0;
}