Cod sursa(job #3172372)

Utilizator N.B.Lnabil. N.B.L Data 20 noiembrie 2023 15:46:23
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

#include <iostream>
#include <vector>

using namespace std;

const int BITS = 21;

struct TrieNode {
    TrieNode *children[2];
    int index;

    TrieNode() {
        children[0] = children[1] = nullptr;
        index = -1;
    }
};

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

pair<int, int> maxXorWithIndex(TrieNode *root, int num) {
    TrieNode *node = root;
    int maxXor = 0;
    for (int i = BITS; i >= 0; i--) {
        int bit = (num >> i) & 1;
        int oppositeBit = bit ^ 1;
        if (node->children[oppositeBit]) {
            maxXor |= (1 << i);
            node = node->children[oppositeBit];
        } else {
            node = node->children[bit];
        }
    }
    return make_pair(maxXor, node->index);
}

int main() {
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

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

    int maxXor = 0, maxXorStart = 0, maxXorEnd = 0, prefixXor = 0;
    for (int i = 0; i < n; i++) {
        prefixXor ^= arr[i];
        pair<int, int> result = maxXorWithIndex(root, prefixXor);
        if (result.first > maxXor) {
            maxXor = result.first;
            maxXorStart = result.second + 1;
            maxXorEnd = i;
        }
        insert(root, prefixXor, i);
    }

    cout << maxXor << " " << maxXorStart + 1 << " " << maxXorEnd + 1 << endl;
    return 0;
}