File size: 2,412 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #include <bits/stdc++.h>
using namespace std;
int main() {
int L, R;
cin >> L >> R;
// Write L and R to a file
FILE* f = fopen("/tmp/testcase.txt", "w");
fprintf(f, "%d %d\n", L, R);
fclose(f);
// Now solve normally to get valid output
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});
}
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;
}
|