Cod sursa(job #3310851)

Utilizator rares89_Dumitriu Rares rares89_ Data 17 septembrie 2025 13:31:09
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <vector>
#include <climits> // INT_MIN

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct TrieNode {
    TrieNode* child[2] = {nullptr, nullptr};
    int index = -1; // indexul prefixului
};

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

pair<int,int> query(TrieNode* root, int num) {
    TrieNode* node = root;
    int res = 0;
    for (int i = 30; i >= 0; --i) {
        int bit = (num >> i) & 1;
        int preferred = 1 - bit;
        if (node -> child[preferred]) {
            res |= (1 << i);
            node = node -> child[preferred];
        } else {
            node = node -> child[bit];
        }
    }
    return {res, node -> index};
}

int main() {
    int N;
    fin >> N;
    
    vector<int> a(N);
    for(int i = 0; i < N; ++i) {
        fin >> a[i];
    }
    
    fin.close();

    vector<int> prefix(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        prefix[i] = prefix[i - 1] ^ a[i - 1];
    }

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

    int max_xor = INT_MIN;
    int start = 1, stop = 1;

    for (int r = 1; r <= N; ++r) {
        auto [val, l_idx] = query(root, prefix[r]);
        if (val > max_xor || (val == max_xor && r < stop) || (val == max_xor && r == stop && l_idx + 1 > start)) {
            max_xor = val;
            start = l_idx + 1;
            stop = r;
        }
        insert(root, prefix[r], r);
    }

    fout << max_xor << " " << start << " " << stop << "\n";
    return 0;
}