Cod sursa(job #3355902)

Utilizator nstefanNeagu Stefan nstefan Data 27 mai 2026 16:09:28
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

struct Element {
    int val;
    int prefix_xor;
    int idx;
};

struct TrieNode {
    TrieNode* children[2] = {nullptr, nullptr};
    int idx = -1;
};

void insert(TrieNode* root, int val, int idx) {
    TrieNode* curr = root;
    for (int i = 30; i >= 0; i--) {
        int bit = (val >> i) & 1;
        if (!curr->children[bit]) {
            curr->children[bit] = new TrieNode();
        }
        curr = curr->children[bit];
    }
    curr->idx = idx;
}

pair<int, int> query(TrieNode* root, int val) {
    TrieNode* curr = root;
    int max_xor = 0;
    for (int i = 30; i >= 0; i--) {
        int bit = (val >> i) & 1;
        int flipped = 1 - bit;
        if (curr->children[flipped]) {
            max_xor |= (1 << i);
            curr = curr->children[flipped];
        } else if (curr->children[bit]) {
            curr = curr->children[bit];
        } else {
            return {-1, -1};
        }
    }
    return {max_xor, curr->idx};
}

int main() {
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

    int n;
    if (!(cin >> n)) return 0;

    vector<Element> arr(n);
    int current_prefix = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i].val;
        current_prefix ^= arr[i].val;
        arr[i].prefix_xor = current_prefix;
        arr[i].idx = i + 1;
    }

    TrieNode* root = new TrieNode();
    insert(root, 0, 0);

    int best_max_xor = -1;
    int best_start = 0;
    int best_end = 0;

    for (int i = 0; i < n; i++) {
        pair<int, int> result = query(root, arr[i].prefix_xor);
        if (result.first > best_max_xor) {
            best_max_xor = result.first;
            best_start = result.second + 1;
            best_end = arr[i].idx;
        }
        insert(root, arr[i].prefix_xor, arr[i].idx);
    }

    cout << best_max_xor << " " << best_start << " " << best_end << "\n";

    return 0;
}