File size: 5,853 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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 | #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 addNode = [&]() { adj.emplace_back(); return n++; };
int END_NODE = addNode();
int START = addNode();
// Free chain
vector<int> F(21, -1);
F[0] = END_NODE;
for (int k = 1; k <= 20; k++) {
F[k] = addNode();
adj[F[k]].push_back({F[k-1], 0});
adj[F[k]].push_back({F[k-1], 1});
}
// Decompose [lo, hi] into aligned blocks at bit length k
auto getAlignedBlocks = [](int lo, int hi, int k) -> vector<pair<int,int>> {
vector<pair<int,int>> blocks;
int x = lo;
while (x <= hi) {
int p = 0;
while (p < k && (x % (1 << (p+1)) == 0) && (x + (1 << (p+1)) - 1 <= hi)) p++;
blocks.push_back({x, p});
x += (1 << p);
}
return blocks;
};
// For a range [lo, hi] at k bits, create a node that uses multi-edges
// to maximize sharing with the free chain.
//
// Key idea: decompose into aligned blocks. For each block with prefix P
// and free length f, instead of building a chain of forced-bit nodes for P,
// have the parent node emit MULTIPLE edges with the same bit value to
// different children, each handling a different aligned sub-block.
map<tuple<int,int,int>, int> memo;
function<int(int, int, int)> buildRange = [&](int k, int lo, int hi) -> int {
if (lo > hi || k < 0) return -1;
if (k == 0) return (lo == 0 && hi == 0) ? END_NODE : -1;
if (lo == 0 && hi == (1 << k) - 1) return F[k];
auto key = make_tuple(k, lo, hi);
if (memo.count(key)) return memo[key];
// Standard binary split
int mid = 1 << (k-1);
// 0-branch: [lo, min(hi, mid-1)] at k-1 bits
int left = -1;
if (lo <= min(hi, mid-1)) {
left = buildRange(k-1, lo, min(hi, mid-1));
}
// 1-branch: [max(lo,mid)-mid, hi-mid] at k-1 bits
int right = -1;
if (max(lo, mid) <= hi) {
right = buildRange(k-1, max(lo, mid) - mid, hi - mid);
}
if (left == -1 && right == -1) return memo[key] = -1;
// Now try multi-edge optimization:
// If left has only one edge (forced bit), and that edge goes to a node
// that we could reach by splitting differently...
// Actually, let's try a different approach: decompose each branch into
// aligned blocks and add multiple edges
// Standard approach (for now)
int u = addNode();
if (left != -1) adj[u].push_back({left, 0});
if (right != -1) adj[u].push_back({right, 1});
return memo[key] = u;
};
// Now the key optimization: for forced-bit chains, replace them with
// multi-edge parents.
//
// Example: if node A has edge (1)->B, and B has edge (0)->C,
// and A's parent P has edge (0)->A,
// then P has path P->(0)->A->(1)->B->(0)->C
// Instead, we could have P directly emit edges to skip A and B:
// P->(0)->C with... but that changes the bit sequence.
//
// This doesn't work for linear chains.
// Alternative: build the range using multi-edge per bit.
// For range [lo, hi] at k bits, decompose into aligned blocks.
// Group blocks by their FIRST BIT:
// bit 0 blocks: those with start < mid (first bit 0)
// bit 1 blocks: those with start >= mid (first bit 1)
// For each group, further decompose by second bit, etc.
// At each level, if a block has a free suffix, connect directly to F[free_len].
//
// This is essentially the trie approach, which gives 55 nodes.
// Let me try: multi-edge from each range node to DIRECTLY connect
// to aligned blocks, potentially skipping multiple forced-bit levels.
// We can have multiple edges with the same weight!
// E.g., node U can have edge (0)->A AND edge (0)->B, as long as
// A and B's languages are disjoint.
//
// This means: instead of U->(0)->chain->(0)->...->(0)->F[k],
// we can have U->(0)->F[k] directly? NO - that changes the number of bits.
//
// Each edge consumes one bit. The chain of forced 0s consumes multiple bits.
// We can't replace multiple edges with one.
int lenL = 32 - __builtin_clz(L);
int 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 suffLen = len - 1;
int loSuf = cL - rs, hiSuf = cR - rs;
int target;
if (suffLen == 0) target = END_NODE;
else target = buildRange(suffLen, loSuf, hiSuf);
if (target >= 0) adj[START].push_back({target, 1});
}
// Remove unreachable
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); }
}
}
map<int,int> newId;
int cnt = 0;
newId[START] = ++cnt;
for (int i = 0; i < n; i++)
if (i != START && reach[i]) newId[i] = ++cnt;
cout << cnt << "\n";
vector<int> inv(cnt + 1);
for (auto& [old, nw] : newId) inv[nw] = old;
for (int i = 1; i <= cnt; i++) {
int u = inv[i];
cout << adj[u].size();
for (auto& e : adj[u]) cout << " " << newId[e.to] << " " << e.w;
cout << "\n";
}
return 0;
}
|