Cod sursa(job #3354340)

Utilizator robert_dumitruDumitru Robert Ionut robert_dumitru Data 17 mai 2026 16:02:42
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <vector>

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

struct Node {
    Node* copii[2];
    int index;

    Node() {
        copii[0] = nullptr;
        copii[1] = nullptr;
        index = -1;
    }

    ~Node() {
        delete copii[0];
        delete copii[1];
    }
};

class Trie {
    Node* root;
public:
    Trie() {
        root = new Node();
    }

    ~Trie() {
        delete root;
    }

    void insert(int numar, int index) {
        Node* curr = root;

        for (int i = 20; i >= 0; i--) {
            int bit = (numar >> i) & 1;

            if (curr->copii[bit] == nullptr) {
                curr->copii[bit] = new Node();
            }
            curr = curr->copii[bit];
        }

        curr->index = index;
    }

    std::pair<int, int> findMax(int numar) {
        Node* curr = root;
        int value = 0;
        for (int i = 20; i >= 0; i--) {
            int bit = (numar >> i) & 1;

            if (curr->copii[bit ^ 1] != nullptr) {
                curr = curr->copii[bit ^ 1];
                value = value * 2 + (bit ^ 1);
            }
            else {
                curr = curr->copii[bit];
                value = value * 2 + bit;
            }
        }
        return std::make_pair(value, curr->index);
    }
};

int n;
int a[100005], aux[100005];

int main() {
    Trie trie;
    int m, l, r, x, y;

    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
    }

    aux[0] = 0;
    m = -1;
    trie.insert(aux[0], 0);

    for (int i = 1; i <= n; i++) {
        aux[i] = aux[i - 1] ^ a[i];
        auto[x, y] = trie.findMax(aux[i]);
        if ((x ^ aux[i]) > m) {
            m = x ^ aux[i];
            l = y; r = i;
        }
        trie.insert(aux[i], i);
    }

    fout << m << " " << l + 1 << " " << r << "\n";
    return 0;
}