Cod sursa(job #3041129)

Utilizator rastervcrastervc rastervc Data 30 martie 2023 23:37:56
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <vector>
#include <tuple>

using namespace std;

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

class Trie {
    struct Node {
        int pos;
        int next[2] = {};
    };
    vector<Node> trie;

public:
    inline Trie() noexcept 
        : trie(1) {}

    inline void insert(int pos, int val) {
        int node = 0;
        for (int bit = 20; bit >= 0; --bit) {
            bool curr = (val & (1 << bit));
            if (trie[node].next[curr] == 0) {
                trie[node].next[curr] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].next[curr];
        }
        trie[node].pos = pos;
    }

    inline tuple<int, int, int> query(int pos, int val) {
        int node = 0, ans = 0;
        for (int bit = 20; bit >= 0; --bit) {
            bool curr = (val & (1 << bit));
            if (trie[node].next[1 - curr] == 0)
                node = trie[node].next[curr];
            else {
                node = trie[node].next[1 - curr];
                ans |= (1 << bit);
            }
        }
        return make_tuple(ans, -pos, trie[node].pos + 1);
    }
};

int main() {
    int N, val, prefix = 0;
    Trie trie;

    tuple<int, int, int> ans = make_tuple(-1, 0, 0);

    fin >> N;
    trie.insert(0, 0);
    for (int i = 1; i <= N; ++i) {
        fin >> val;
        prefix ^= val;
        ans = max(ans, trie.query(i, prefix));
        trie.insert(i, prefix);
    }

    fout << get<0>(ans) << ' ' << get<2>(ans) << ' ' << -get<1>(ans);

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