docker_space/frontier_cs_7/solution2.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, R;
    cin >> L >> R;

    // Build ADFA recognizing binary representations of [L,R]
    // Then minimize by merging nodes with identical subtrees (right languages)

    struct Edge { int to, w; };

    // Phase 1: Build all nodes
    vector<vector<Edge>> adj;
    int n = 0;
    auto nn = [&]() -> int { adj.emplace_back(); return n++; };

    int END = nn(); // 0
    int START = nn(); // 1

    // Free chain: free[k] accepts any k-bit suffix
    map<int,int> fc;
    fc[0] = END;
    function<int(int)> getF = [&](int k) -> int {
        if (fc.count(k)) return fc[k];
        int ch = getF(k-1), u = nn();
        adj[u].push_back({ch, 0});
        adj[u].push_back({ch, 1});
        return fc[k] = u;
    };

    // Range nodes: gr(k, lo, hi) accepts k-bit suffixes in [lo, hi]
    map<tuple<int,int,int>,int> rc;
    function<int(int,int,int)> gr = [&](int k, int lo, int hi) -> int {
        if (lo > hi) return -1;
        if (k == 0) return (lo == 0 && hi == 0) ? END : -1;
        if (lo == 0 && hi == (1<<k)-1) return getF(k);
        auto key = make_tuple(k, lo, hi);
        auto it = rc.find(key);
        if (it != rc.end()) return it->second;
        int mid = 1 << (k-1);
        int left = -1, right = -1;
        if (lo <= min(hi, mid-1))
            left = gr(k-1, lo, min(hi, mid-1));
        if (max(lo, mid) <= hi)
            right = gr(k-1, max(lo, mid) - mid, hi - mid);
        if (left == -1 && right == -1) return rc[key] = -1;
        int u = nn();
        if (left != -1) adj[u].push_back({left, 0});
        if (right != -1) adj[u].push_back({right, 1});
        return rc[key] = u;
    };

    int lenL = 32 - __builtin_clz(L), lenR = 32 - __builtin_clz(R);
    for (int len = lenL; len <= lenR; len++) {
        int rs = 1 << (len-1), re = (1<<len)-1;
        int cL = max(L, rs), cR = min(R, re);
        if (cL > cR) continue;
        int target;
        if (len == 1) target = END;
        else target = gr(len-1, cL - rs, cR - rs);
        if (target != -1)
            adj[START].push_back({target, 1});
    }

    // Phase 2: Compute reachability from START
    vector<bool> reach(n, false);
    {
        queue<int> q;
        q.push(START);
        reach[START] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : adj[u]) {
                if (!reach[e.to]) {
                    reach[e.to] = true;
                    q.push(e.to);
                }
            }
        }
    }

    // Phase 3: ADFA minimization - merge nodes with identical subtrees
    // Compute signature for each node bottom-up (topological order)
    // Signature = sorted list of (child_signature, weight) pairs

    // Compute topological order (reverse BFS from END, or compute in-degrees)
    // Actually, let's use the fact that this is a layered DAG.
    // We'll compute signatures bottom-up.

    // First, compute depth of each node (longest path from node to END)
    vector<int> depth(n, -1);
    depth[END] = 0;
    // BFS in reverse topological order
    // Let's compute topological order first
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++) {
        if (!reach[u]) continue;
        for (auto& e : adj[u]) {
            indeg[e.to]++;
        }
    }
    vector<int> topo;
    queue<int> q;
    for (int u = 0; u < n; u++) {
        if (reach[u] && indeg[u] == 0) q.push(u);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto& e : adj[u]) {
            if (--indeg[e.to] == 0) q.push(e.to);
        }
    }

    // Reverse topological order for bottom-up processing
    reverse(topo.begin(), topo.end());

    // Compute canonical signature for each node
    // Map signature -> representative node
    map<vector<pair<int,int>>, int> sig_to_rep; // signature -> representative
    vector<int> node_rep(n, -1); // node -> its representative

    for (int u : topo) {
        if (!reach[u]) continue;
        // Build signature using representative IDs of children
        vector<pair<int,int>> sig;
        for (auto& e : adj[u]) {
            sig.push_back({node_rep[e.to], e.w});
        }
        sort(sig.begin(), sig.end());

        auto it = sig_to_rep.find(sig);
        if (it != sig_to_rep.end()) {
            node_rep[u] = it->second;
        } else {
            node_rep[u] = u;
            sig_to_rep[sig] = u;
        }
    }

    // But wait - START must remain START (can't merge with anything else due to its role)
    // And END must remain END.
    // Actually, the merging is fine as long as we track which nodes survive.

    // However, there's a subtlety: we can't merge START with anything because it's the
    // unique in-degree-0 node. Similarly END is the unique out-degree-0 node.
    // The signature-based merging handles this naturally if signatures are truly identical.

    // Collect unique representative nodes
    set<int> reps;
    for (int u : topo) {
        if (reach[u]) reps.insert(node_rep[u]);
    }

    // Assign new IDs. START must be first.
    map<int, int> new_id;
    int cnt = 0;
    new_id[node_rep[START]] = ++cnt;
    for (int r : reps) {
        if (r != node_rep[START]) {
            new_id[r] = ++cnt;
        }
    }

    // Build output adjacency
    vector<vector<pair<int,int>>> out_adj(cnt + 1);
    for (int r : reps) {
        int id = new_id[r];
        for (auto& e : adj[r]) {
            int child_rep = node_rep[e.to];
            out_adj[id].push_back({new_id[child_rep], e.w});
        }
        // Deduplicate edges
        sort(out_adj[id].begin(), out_adj[id].end());
        out_adj[id].erase(unique(out_adj[id].begin(), out_adj[id].end()), out_adj[id].end());
    }

    cout << cnt << "\n";
    for (int i = 1; i <= cnt; i++) {
        cout << out_adj[i].size();
        for (auto& [to, w] : out_adj[i]) {
            cout << " " << to << " " << w;
        }
        cout << "\n";
    }

    return 0;
}