File size: 2,982 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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | #include <bits/stdc++.h>
using namespace std;
int main() {
int L = 577837, R = 979141;
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)> 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;
};
map<tuple<int,int,int>,int> rc;
vector<tuple<int,int,int>> node_info; // what (k,lo,hi) each node represents
node_info.resize(2); // END and START
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();
node_info.resize(n);
node_info[u] = key;
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 = (len == 1) ? END : gr(len-1, cL - rs, cR - rs);
if (target != -1) adj[START].push_back({target, 1});
}
// Count reachable
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); }
}
}
int cnt = 0;
for (int i = 0; i < n; i++) if (reach[i]) cnt++;
cout << "Total reachable nodes: " << cnt << endl;
// Print all range nodes
cout << "Free chain nodes: ";
for (auto& [k, id] : fc) cout << "F[" << k << "]=" << id << " ";
cout << endl;
cout << "Range nodes:" << endl;
for (auto& [key, id] : rc) {
auto [k, lo, hi] = key;
if (reach[id] || id == -1) {
cout << " (" << k << ", " << lo << ", " << hi << ") -> node " << id;
if (id >= 0 && reach[id]) {
cout << " edges:";
for (auto& e : adj[id]) cout << " (" << e.to << "," << e.w << ")";
}
cout << endl;
}
}
return 0;
}
|