File size: 3,122 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 96 97 98 99 100 101 102 103 104 105 106 | #include <bits/stdc++.h>
using namespace std;
struct Node {
vector<pair<int,int>> edges; // (to, label 0/1)
int next_trie[2];
Node() { next_trie[0] = next_trie[1] = 0; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long L, R;
if (!(cin >> L >> R)) return 0;
vector<pair<long long,int>> blocks; // (base, k) covering [base, base + 2^k - 1]
long long x = L;
while (x <= R) {
int k = 0;
while (true) {
long long nextk = k + 1;
long long size = 1LL << nextk;
if ((x & (size - 1)) == 0 && x + size - 1 <= R) k = nextk;
else break;
}
blocks.emplace_back(x, k);
x += (1LL << k);
}
int maxk = 0;
for (auto &b : blocks) maxk = max(maxk, b.second);
vector<Node> nodes;
nodes.reserve(500);
nodes.push_back(Node()); // dummy to make 1-based
int START = 1;
nodes.push_back(Node()); // node 1: start
int T = (int)nodes.size(); // terminal
nodes.push_back(Node()); // node T
// T has outdegree 0
// Build suffix chain nodes: Suf[d] means remaining d bits to emit arbitrarily
vector<int> Suf(maxk + 1, 0); // Suf[0] unused, Suf[d] node id
// We will build increasing d so transitions go to lower d
for (int d = 1; d <= maxk; ++d) {
int id = (int)nodes.size();
nodes.push_back(Node());
Suf[d] = id;
int to = (d == 1 ? T : Suf[d-1]);
// edges for both labels
nodes[id].edges.emplace_back(to, 0);
nodes[id].edges.emplace_back(to, 1);
}
auto ensure_child = [&](int u, int b) {
if (nodes[u].next_trie[b] == 0) {
int v = (int)nodes.size();
nodes.push_back(Node());
nodes[u].next_trie[b] = v;
nodes[u].edges.emplace_back(v, b);
}
return nodes[u].next_trie[b];
};
auto bits_of = [&](long long p) {
vector<int> bits;
while (p > 0) { bits.push_back((int)(p & 1)); p >>= 1; }
reverse(bits.begin(), bits.end());
if (bits.empty()) bits.push_back(0); // shouldn't happen for p>=1
return bits;
};
for (auto &blk : blocks) {
long long base = blk.first;
int k = blk.second;
long long p = base >> k; // prefix
vector<int> bits = bits_of(p); // MSB to LSB
int u = START;
int m = (int)bits.size();
for (int i = 0; i < m - 1; ++i) {
u = ensure_child(u, bits[i]);
}
int lastb = bits[m - 1];
// ensure trie child for deeper prefixes
int v = ensure_child(u, lastb);
// add extra parallel edge for this block to suffix or terminal
int dest = (k > 0 ? Suf[k] : T);
nodes[u].edges.emplace_back(dest, lastb);
}
int n = (int)nodes.size() - 1;
cout << n << "\n";
for (int i = 1; i <= n; ++i) {
int k = (int)nodes[i].edges.size();
cout << k;
for (auto &e : nodes[i].edges) {
cout << " " << e.first << " " << e.second;
}
cout << "\n";
}
return 0;
} |