Cod sursa(job #3234217)

Utilizator elbarosPetre Tudor elbaros Data 7 iunie 2024 22:46:33
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

int n, res = -1, start, stop;

struct Trie {
    Trie* son[2];
    int pos;

    Trie() {
        son[0] = son[1] = nullptr;
        pos = 0;
    }
};
Trie* root = new Trie();

void insert(Trie* node, int val, int bitPos, int vecPos) {
    if (bitPos == -1) {
        node->pos = vecPos;
        return;
    }

    int bit = (val & (1 << bitPos)) > 0;
    if (node->son[bit] == nullptr) {
        node->son[bit] = new Trie();
    }

    insert(node->son[bit], val, bitPos - 1, vecPos);
}

pair<int, int> query(Trie* node, int val, int bitPos) {
    if (bitPos == -1) {
        return make_pair(0, node->pos);
    }
    
    int bit = (val & (1 << bitPos)) > 0;
    pair<int, int> res;
    if (node->son[bit ^ 1] != nullptr) {
        res = query(node->son[bit ^ 1], val, bitPos - 1);
        res.first += (1 << bitPos);
    } else {
        res = query(node->son[bit], val, bitPos - 1);
    }
    return res;
}

int main() {
    ifstream in("xormax.in");
    ofstream out("xormax.out");

    insert(root, 0, 20, 0);
    int sumXor = 0;

    in >> n;
    for (int i = 1; i <= n; i++) {
        int val;
        in >> val;
        sumXor ^= val;
        auto crtRes = query(root, sumXor, 20);
        if (crtRes.first > res) {
            res = crtRes.first;
            start = crtRes.second + 1;
            stop = i;
        }
        insert(root, sumXor, 20, i);
    }

    out << res << " " << start << " " << stop << "\n";
    return 0;
}