docker_space/frontier_cs_7/solution.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 nn = [&]() -> int { adj.emplace_back(); return ++n; };

    int END = nn();
    int START = nn();

    map<int,int> fc;
    fc[0] = END;
    function<int(int)> gf = [&](int k) -> int {
        if (fc.count(k)) return fc[k];
        int ch = gf(k-1), u = nn();
        adj[u-1].push_back({ch,0}); adj[u-1].push_back({ch,1});
        return fc[k] = u;
    };

    map<tuple<int,int,int>,int> rc;
    function<int(int,int,int)> gr = [&](int k, int lo, int hi) -> int {
        if (lo > hi) return 0;
        if (k == 0) return (lo==0&&hi==0) ? END : 0;
        if (lo==0 && hi==(1<<k)-1) return gf(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 = (lo<=min(hi,mid-1)) ? gr(k-1,lo,min(hi,mid-1)) : 0;
        int right = (max(lo,mid)<=hi) ? gr(k-1,max(lo,mid)-mid,hi-mid) : 0;
        if (!left && !right) return rc[key] = 0;
        int u = nn();
        if (left) adj[u-1].push_back({left,0});
        if (right) adj[u-1].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, cL=max(L,rs), cR=min(R,re);
        if (cL>cR) continue;
        int target = (len==1)?END:gr(len-1,cL-rs,cR-rs);
        if (target) adj[START-1].push_back({target,1});
    }

    // Remove unreachable
    vector<bool> reach(n+1,false);
    queue<int> bfs;
    bfs.push(START); reach[START]=true;
    while(!bfs.empty()){int u=bfs.front();bfs.pop();for(auto&e:adj[u-1])if(!reach[e.to]){reach[e.to]=true;bfs.push(e.to);}}

    vector<int> nid(n+1,0);
    int cnt=0;
    nid[START]=++cnt;
    for(int i=1;i<=n;i++) if(i!=START&&reach[i]) nid[i]=++cnt;

    cout<<cnt<<"\n";
    vector<int> inv(cnt+1);
    for(int i=1;i<=n;i++) if(reach[i]) inv[nid[i]]=i;
    for(int i=1;i<=cnt;i++){
        int u=inv[i]; cout<<adj[u-1].size();
        for(auto&e:adj[u-1]) cout<<" "<<nid[e.to]<<" "<<e.w;
        cout<<"\n";
    }
    return 0;
}