docker_space/frontier_cs_7/solution_dp.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int L, R;
    cin >> L >> R;
    
    // Find bit lengths
    int lenL = (L == 0) ? 1 : 32 - __builtin_clz(L);
    int lenR = (R == 0) ? 1 : 32 - __builtin_clz(R);
    
    struct Edge { int to, w; };
    vector<vector<Edge>> adj;
    int n = 0;
    auto addNode = [&]() { adj.emplace_back(); return n++; };
    
    int END = addNode(); // 0
    int START = addNode(); // 1
    
    // Free chain
    map<int,int> freeNode;
    freeNode[0] = END;
    function<int(int)> getFree = [&](int k) -> int {
        if (freeNode.count(k)) return freeNode[k];
        int ch = getFree(k-1);
        int u = addNode();
        adj[u].push_back({ch, 0});
        adj[u].push_back({ch, 1});
        return freeNode[k] = u;
    };
    
    // For each bit length, build the sub-DAG
    // State: (position, tight_lo, tight_hi)
    // position: current bit position (0 = MSB after the leading 1)
    // tight_lo: still matching L's bits
    // tight_hi: still matching R's bits
    
    for (int len = lenL; len <= lenR; len++) {
        int rs = 1 << (len-1);
        int re = (1 << len) - 1;
        int cL = max(L, rs);
        int cR = min(R, re);
        if (cL > cR) continue;
        
        int suffLen = len - 1; // bits after MSB
        int loSuf = cL - rs;
        int hiSuf = cR - rs;
        
        // Extract bits
        vector<int> loBits(suffLen), hiBits(suffLen);
        for (int i = 0; i < suffLen; i++) {
            loBits[i] = (loSuf >> (suffLen - 1 - i)) & 1;
            hiBits[i] = (hiSuf >> (suffLen - 1 - i)) & 1;
        }
        
        // Build DP
        // States: (pos, tight_lo, tight_hi)
        // For memoization, use a map
        // Node IDs for each state
        map<tuple<int,bool,bool>, int> stateNode;
        
        function<int(int, bool, bool)> build = [&](int pos, bool tlo, bool thi) -> int {
            if (pos == suffLen) return END;
            
            auto key = make_tuple(pos, tlo, thi);
            auto it = stateNode.find(key);
            if (it != stateNode.end()) return it->second;
            
            if (!tlo && !thi) {
                // Free state
                return stateNode[key] = getFree(suffLen - pos);
            }
            
            int lo_bit = tlo ? loBits[pos] : 0;
            int hi_bit = thi ? hiBits[pos] : 1;
            
            // Enumerate valid bits
            struct ChildInfo { int bit; int nextNode; };
            vector<ChildInfo> children;
            
            for (int b = lo_bit; b <= hi_bit; b++) {
                bool next_tlo = tlo && (b == loBits[pos]);
                bool next_thi = thi && (b == hiBits[pos]);
                int child = build(pos + 1, next_tlo, next_thi);
                children.push_back({b, child});
            }
            
            if (children.empty()) return stateNode[key] = -1;
            
            // Check if this is equivalent to a free node
            if (children.size() == 2 && children[0].nextNode == children[1].nextNode 
                && children[0].nextNode == getFree(suffLen - pos - 1)) {
                return stateNode[key] = getFree(suffLen - pos);
            }
            
            int u = addNode();
            for (auto& c : children) {
                adj[u].push_back({c.nextNode, c.bit});
            }
            return stateNode[key] = u;
        };
        
        int root = build(0, loSuf != 0 || true, hiSuf != ((1 << suffLen) - 1) || true);
        // Actually, always start tight
        root = build(0, true, true);
        if (root >= 0) {
            adj[START].push_back({root, 1});
        }
    }
    
    // Remove unreachable
    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 (e.to >= 0 && !reach[e.to]) {
                reach[e.to] = true;
                q.push(e.to);
            }
        }
    }
    
    // Renumber
    map<int,int> newId;
    int cnt = 0;
    newId[START] = ++cnt;
    for (int i = 0; i < n; i++) {
        if (i != START && reach[i]) newId[i] = ++cnt;
    }
    
    cout << cnt << "\n";
    vector<int> inv(cnt + 1);
    for (auto& [old, nw] : newId) inv[nw] = old;
    for (int i = 1; i <= cnt; i++) {
        int u = inv[i];
        vector<pair<int,int>> edges;
        for (auto& e : adj[u]) {
            if (newId.count(e.to)) {
                edges.push_back({newId[e.to], e.w});
            }
        }
        cout << edges.size();
        for (auto& [to, w] : edges) cout << " " << to << " " << w;
        cout << "\n";
    }
    
    return 0;
}