Cod sursa(job #3354719)

Utilizator fmi-studentnu sunt de acord fmi-student Data 19 mai 2026 22:49:51
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

struct Node {
    int next[2];
    int prefix_index;
};

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

private:
    vector<Node> tree;
    int next_free_node;

    int create_node() {
        if (next_free_node >= tree.size()) {
            tree.push_back({{-1, -1}, -1});
        } else {
            tree[next_free_node] = {{-1, -1}, -1};
        }
        return next_free_node++;
    }

public:
    FlatTrie(int estimated_size) {
        tree.reserve(estimated_size);
        next_free_node = 0;
        create_node(); 
    }

    void insert(int val, int idx) {
        int current_node = 0; 
        for (int bit = MAX_BIT; bit >= 0; --bit) {
            int i = (val >> bit) & 1;
            
            if (tree[current_node].next[i] == -1) {
                tree[current_node].next[i] = create_node();
            }
            
            current_node = tree[current_node].next[i];
        }
        tree[current_node].prefix_index = idx;
    }

    pair<int, int> find_best(int val) const {
        int current_node = 0;
        int best_xor = 0;
        
        for (int bit = MAX_BIT; bit >= 0; --bit) {
            int i = (val >> bit) & 1;
            int desired = 1 - i;
            
            if (tree[current_node].next[desired] != -1) {
                best_xor |= (1 << bit);
                current_node = tree[current_node].next[desired];
            } else {
                current_node = tree[current_node].next[i];
            }
        }
        
        return {best_xor, tree[current_node].prefix_index};
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    int n;
    fin >> n;
    FlatTrie trie(n * (FlatTrie::MAX_BIT + 1) + 1);
    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";

    return 0;
}