docker_space/frontier_cs_7/solution4.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int L, R;
    cin >> L >> R;
    
    struct Edge { int to, w; };
    vector<vector<Edge>> adj;
    int n = 0;
    auto addNode = [&]() { adj.emplace_back(); return n++; };
    
    int END_NODE = addNode();
    int START = addNode();
    
    // Free chain
    vector<int> F(21, -1);
    F[0] = END_NODE;
    for (int k = 1; k <= 20; k++) {
        F[k] = addNode();
        adj[F[k]].push_back({F[k-1], 0});
        adj[F[k]].push_back({F[k-1], 1});
    }
    
    // Decompose [lo, hi] into aligned blocks at bit length k
    auto getAlignedBlocks = [](int lo, int hi, int k) -> vector<pair<int,int>> {
        vector<pair<int,int>> blocks;
        int x = lo;
        while (x <= hi) {
            int p = 0;
            while (p < k && (x % (1 << (p+1)) == 0) && (x + (1 << (p+1)) - 1 <= hi)) p++;
            blocks.push_back({x, p});
            x += (1 << p);
        }
        return blocks;
    };
    
    // For a range [lo, hi] at k bits, create a node that uses multi-edges
    // to maximize sharing with the free chain.
    //
    // Key idea: decompose into aligned blocks. For each block with prefix P
    // and free length f, instead of building a chain of forced-bit nodes for P,
    // have the parent node emit MULTIPLE edges with the same bit value to
    // different children, each handling a different aligned sub-block.
    
    map<tuple<int,int,int>, int> memo;
    
    function<int(int, int, int)> buildRange = [&](int k, int lo, int hi) -> int {
        if (lo > hi || k < 0) return -1;
        if (k == 0) return (lo == 0 && hi == 0) ? END_NODE : -1;
        if (lo == 0 && hi == (1 << k) - 1) return F[k];
        
        auto key = make_tuple(k, lo, hi);
        if (memo.count(key)) return memo[key];
        
        // Standard binary split
        int mid = 1 << (k-1);
        
        // 0-branch: [lo, min(hi, mid-1)] at k-1 bits
        int left = -1;
        if (lo <= min(hi, mid-1)) {
            left = buildRange(k-1, lo, min(hi, mid-1));
        }
        
        // 1-branch: [max(lo,mid)-mid, hi-mid] at k-1 bits
        int right = -1;
        if (max(lo, mid) <= hi) {
            right = buildRange(k-1, max(lo, mid) - mid, hi - mid);
        }
        
        if (left == -1 && right == -1) return memo[key] = -1;
        
        // Now try multi-edge optimization:
        // If left has only one edge (forced bit), and that edge goes to a node
        // that we could reach by splitting differently...
        // Actually, let's try a different approach: decompose each branch into
        // aligned blocks and add multiple edges
        
        // Standard approach (for now)
        int u = addNode();
        if (left != -1) adj[u].push_back({left, 0});
        if (right != -1) adj[u].push_back({right, 1});
        
        return memo[key] = u;
    };
    
    // Now the key optimization: for forced-bit chains, replace them with
    // multi-edge parents.
    //
    // Example: if node A has edge (1)->B, and B has edge (0)->C,
    // and A's parent P has edge (0)->A,
    // then P has path P->(0)->A->(1)->B->(0)->C
    // Instead, we could have P directly emit edges to skip A and B:
    // P->(0)->C with... but that changes the bit sequence.
    //
    // This doesn't work for linear chains.
    
    // Alternative: build the range using multi-edge per bit.
    // For range [lo, hi] at k bits, decompose into aligned blocks.
    // Group blocks by their FIRST BIT:
    //   bit 0 blocks: those with start < mid (first bit 0)
    //   bit 1 blocks: those with start >= mid (first bit 1)
    // For each group, further decompose by second bit, etc.
    // At each level, if a block has a free suffix, connect directly to F[free_len].
    //
    // This is essentially the trie approach, which gives 55 nodes.
    
    // Let me try: multi-edge from each range node to DIRECTLY connect
    // to aligned blocks, potentially skipping multiple forced-bit levels.
    
    // We can have multiple edges with the same weight!
    // E.g., node U can have edge (0)->A AND edge (0)->B, as long as
    // A and B's languages are disjoint.
    //
    // This means: instead of U->(0)->chain->(0)->...->(0)->F[k],
    // we can have U->(0)->F[k] directly? NO - that changes the number of bits.
    //
    // Each edge consumes one bit. The chain of forced 0s consumes multiple bits.
    // We can't replace multiple edges with one.
    
    int lenL = 32 - __builtin_clz(L);
    int 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 suffLen = len - 1;
        int loSuf = cL - rs, hiSuf = cR - rs;
        
        int target;
        if (suffLen == 0) target = END_NODE;
        else target = buildRange(suffLen, loSuf, hiSuf);
        
        if (target >= 0) adj[START].push_back({target, 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 (!reach[e.to]) { reach[e.to] = true; q.push(e.to); }
        }
    }
    
    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];
        cout << adj[u].size();
        for (auto& e : adj[u]) cout << " " << newId[e.to] << " " << e.w;
        cout << "\n";
    }
    
    return 0;
}