File size: 2,754 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 | #include <bits/stdc++.h>
using namespace std;
vector<int> get_bits(long long x) {
vector<int> res;
if (x == 0) return res;
while (x > 0) {
res.push_back(x % 2);
x /= 2;
}
reverse(res.begin(), res.end());
return res;
}
int main() {
long long L, R;
cin >> L >> R;
int node_cnt = 1; // 1 is root
int endn = ++node_cnt; // 2 is end
vector<int> fulls(21, -1);
fulls[0] = endn;
function<int(int)> get_full = [&](int rem) -> int {
if (fulls[rem] != -1) return fulls[rem];
if (rem == 0) return fulls[0];
int nd = ++node_cnt;
int nxt = get_full(rem - 1);
// We will add edges later? No, add here.
// But since vector not yet, wait, g not defined.
// Wait, move g inside.
return fulls[rem] = nd; // Temporarily, add edges after all? No.
// Problem: g not defined yet.
};
// Better define g now.
vector<vector<pair<int, int>>> g(105);
// Now redefine get_full with g.
auto get_full_lambda = [&](auto&& self, int rem) -> int {
if (fulls[rem] != -1) return fulls[rem];
if (rem == 0) return fulls[0];
int nd = ++node_cnt;
int nxt = self(self, rem - 1);
g[nd].emplace_back(nxt, 0);
g[nd].emplace_back(nxt, 1);
return fulls[rem] = nd;
};
vector<pair<long long, int>> blocks;
long long cur = L;
while (cur <= R) {
long long remn = R - cur + 1;
int k = 0;
while ((1LL << (k + 1)) <= remn && (cur % (1LL << (k + 1))) == 0) ++k;
blocks.emplace_back(cur, k);
cur += (1LL << k);
}
for (auto [st, kk] : blocks) {
long long pre = st >> kk;
vector<int> bits = get_bits(pre);
int m = bits.size();
int target = get_full_lambda(get_full_lambda, kk);
int current = 1;
for (int i = 0; i < m; ++i) {
int bitv = bits[i];
int nxt;
if (i == m - 1) {
nxt = target;
} else {
nxt = ++node_cnt;
}
// Check if edge already exists
bool exists = false;
for (auto& p : g[current]) {
if (p.first == nxt && p.second == bitv) {
exists = true;
break;
}
}
if (!exists) {
g[current].emplace_back(nxt, bitv);
}
current = nxt;
}
}
int n = node_cnt;
cout << n << endl;
for (int i = 1; i <= n; ++i) {
int k = g[i].size();
cout << k;
for (auto& p : g[i]) {
cout << " " << p.first << " " << p.second;
}
cout << endl;
}
return 0;
} |