File size: 4,153 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 | #include <iostream>
#include <vector>
#include <map>
#include <tuple>
#include <algorithm>
using namespace std;
// Structure to represent an outgoing edge
struct Edge {
int to;
int weight;
};
// Global variables
// Node 1 is the Source, Node 2 is the Sink.
int N_nodes = 2;
vector<Edge> adj[105]; // Adjacency list for the graph (max 100 nodes allowed)
// Memoization map to share nodes for identical sub-problems
// Key: (number of bits, min value of suffix, max value of suffix)
map<tuple<int, long long, long long>, int> memo;
// Recursive function to construct the DAG nodes
// k: number of bits to generate
// low, high: the range of integer values that the generated k-bit sequence must fall into
int get_node(int k, long long low, long long high) {
// If the requested range is invalid, no path exists
if (low > high) return 0;
// Clamp the range to valid k-bit integer values [0, 2^k - 1]
long long max_val = (1LL << k) - 1;
low = max(0LL, low);
high = min(max_val, high);
if (low > high) return 0;
// Base case: 0 bits remaining. We have successfully formed a valid suffix.
// Return the unique Sink node (index 2).
if (k == 0) return 2;
// Check memoization table
auto key = make_tuple(k, low, high);
if (memo.count(key)) return memo[key];
long long M = 1LL << (k - 1);
// Determine the required ranges for the children
// If we pick edge '0', the remaining (k-1) bits must form a value v such that
// 0*2^(k-1) + v is in [low, high]. So v in [low, high] intersect [0, M-1].
long long l0 = low;
long long h0 = min(high, M - 1);
// If we pick edge '1', the remaining (k-1) bits must form a value v such that
// 1*2^(k-1) + v is in [low, high]. So v in [low - M, high - M] intersect [0, M-1].
// Note: low and high are relative to current k-bit frame.
long long l1 = max(low, M) - M;
long long h1 = high - M;
// Recursively get child nodes
int u0 = 0, u1 = 0;
if (l0 <= h0) u0 = get_node(k - 1, l0, h0);
if (l1 <= h1) u1 = get_node(k - 1, l1, h1);
// If neither path leads to the sink, this node is not needed
if (u0 == 0 && u1 == 0) return 0;
// Allocate a new node
int id = ++N_nodes;
if (u0 != 0) adj[id].push_back({u0, 0});
if (u1 != 0) adj[id].push_back({u1, 1});
// Store in memo and return
return memo[key] = id;
}
int main() {
// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long L, R;
if (!(cin >> L >> R)) return 0;
// Helper lambda to calculate bit length of a positive integer
auto get_len = [&](long long x) {
if (x == 0) return 0;
return 64 - __builtin_clzll(x);
};
int lenL = get_len(L);
int lenR = get_len(R);
// Iterate through each possible bit length in the range [L, R]
// Since leading zeros are not allowed, we process each length separately.
// Numbers of different lengths are distinct, so paths will be unique.
for (int len = lenL; len <= lenR; ++len) {
// Determine the sub-range of [L, R] that has exactly 'len' bits
long long start_range = (len == lenL) ? L : (1LL << (len - 1));
long long end_range = (len == lenR) ? R : (1LL << len) - 1;
if (start_range > end_range) continue;
// For a number with 'len' bits, the MSB must be '1'.
// We add an edge '1' from Source, and the subsequent path must generate
// the remaining len-1 bits matching the suffix value.
long long suffix_start = start_range - (1LL << (len - 1));
long long suffix_end = end_range - (1LL << (len - 1));
int child = get_node(len - 1, suffix_start, suffix_end);
if (child != 0) {
adj[1].push_back({child, 1});
}
}
// Output the result
cout << N_nodes << "\n";
for (int i = 1; i <= N_nodes; ++i) {
cout << adj[i].size();
for (auto& e : adj[i]) {
cout << " " << e.to << " " << e.weight;
}
cout << "\n";
}
return 0;
} |