File size: 3,039 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 | #include <iostream>
#include <vector>
#include <map>
#include <tuple>
#include <algorithm>
using namespace std;
// Represents a directed edge
struct Edge {
int weight;
int to;
};
// Global variables to store graph and memoization
// Node 1 is the Start node.
// Node 2 is the End node (Sink).
int node_count = 2;
map<tuple<int, long long, long long>, int> memo;
vector<Edge> adj[105]; // Max nodes limit is 100, so 105 is safe.
// Function to get or create a node representing the range [l, r] with bit height k.
// Returns the node index.
int get_node(int k, long long l, long long r) {
// Base case: height 0 means we have consumed all bits, so we reach the Sink.
if (k == 0) return 2;
// Check if such a node already exists
auto state = make_tuple(k, l, r);
if (memo.count(state)) return memo[state];
// Create new node
int id = ++node_count;
memo[state] = id;
long long mid = 1LL << (k - 1);
// Determine edges. The current range [l, r] is a subset of [0, 2^k - 1].
// We split this range into lower half [0, mid-1] (edge '0') and upper half [mid, 2^k - 1] (edge '1').
// If [l, r] overlaps with lower half
if (l < mid) {
long long next_r = min(r, mid - 1);
// The values map directly to the next level
int target = get_node(k - 1, l, next_r);
adj[id].push_back({0, target});
}
// If [l, r] overlaps with upper half
if (r >= mid) {
long long next_l = max(l, mid) - mid;
long long next_r = r - mid;
// The values are reduced by 'mid' for the next level
int target = get_node(k - 1, next_l, next_r);
adj[id].push_back({1, target});
}
return id;
}
int main() {
// Optimize I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int L_in, R_in;
if (!(cin >> L_in >> R_in)) return 0;
// We process each bit length separately to ensure no leading zeros.
// The range [L, R] is contained in [1, 10^6]. 10^6 < 2^20, so max length is 20.
for (int len = 1; len <= 20; ++len) {
long long lower = 1LL << (len - 1);
long long upper = (1LL << len) - 1;
long long curL = max((long long)L_in, lower);
long long curR = min((long long)R_in, upper);
if (curL > curR) continue;
// Valid integers in [L, R] with length 'len'.
// The first bit is always '1'.
// The remaining len-1 bits form suffixes in the range [curL - lower, curR - lower].
int target = get_node(len - 1, curL - lower, curR - lower);
// Add edge from Start node (1) with weight 1
adj[1].push_back({1, target});
}
// Output the graph in the specified format
cout << node_count << "\n";
for (int i = 1; i <= node_count; ++i) {
cout << adj[i].size();
for (const auto &e : adj[i]) {
cout << " " << e.to << " " << e.weight;
}
cout << "\n";
}
return 0;
} |