Cod sursa(job #3354453)

Utilizator fmi-studentnu sunt de acord fmi-student Data 18 mai 2026 11:39:46
Problema Xor Max Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <iostream>
#include <cassert>
#include <memory>
#include <vector>
#include <fstream>
using namespace std;

class Trie {
public:
    static const int MAX_BIT = 20;

protected:
    class Node {
    protected:
        int value;
        int prefix_index;
        vector<shared_ptr<Node>> next;

    public:
        Node(int value) : 
            value(value), 
            prefix_index(-1), 
            next(2, nullptr) {}

        void set_prefix_index(int idx) { 
            prefix_index = idx; 
        }
        int get_prefix_index() const { 
            return prefix_index; 
        }

        shared_ptr<Node> get_node(size_t i) const { 
            return next[i]; 
        }
        void add_node(size_t i, int val) {
            next[i] = make_shared<Node>(val);
        }
    };

    shared_ptr<Node> root;

public:
    Trie() : root(make_shared<Node>(-1)) {}

    void insert(int val, int idx) {
        shared_ptr<Node> parser = root;
        for (int bit = MAX_BIT; bit >= 0; --bit) {
            size_t i = (val >> bit) & 1;
            if (!parser->get_node(i)) 
                parser->add_node(i, i);
            
            parser = parser->get_node(i);
        }
        
        parser->set_prefix_index(idx);
    }

    pair<int, int> find_best(int val) {
        shared_ptr<Node> parser = root;
        int best_xor = 0;
        for (int bit = MAX_BIT; bit >= 0; --bit) {
            size_t i = (val >> bit) & 1;
            // vrem opusul
            size_t desired = 1 - i;
            
            if (parser->get_node(desired)) {
                best_xor |= (1 << bit);
                parser = parser->get_node(desired);
            } else {
                parser = parser->get_node(i);
            }
        }

        return {best_xor, parser->get_prefix_index()};
    }
};

int main() {
    ifstream fin("xormax.in");
    if (!fin.is_open()) {
        cerr << "xormax.in failed to open!" << endl;
        return 1;
    }

    ofstream fout("xormax.out");
    if (!fout.is_open()) {
        cerr << "xormax.out failed to open!" << endl;
        return 2;
    }

    int n;
    if (!(fin >> n)) {
        return 0;
    }

    Trie trie;
    trie.insert(0, 0);

    int current_prefix = 0;
    int max_xor = -1;
    int start_pos = -1;
    int end_pos = -1;

    for (int j = 1; j <= n; ++j) {
        int val;
        fin >> val;
        current_prefix ^= val;

        auto [best_xor, best_index] = trie.find_best(current_prefix);
        
        if (best_xor > max_xor) {
            max_xor = best_xor;
            start_pos = best_index + 1;
            end_pos = j;
        }

        trie.insert(current_prefix, j);
    }

    fout << max_xor << " " << start_pos << " " << end_pos << "\n";

    fin.close();
    fout.close();    
    return 0;
}