docker_space/frontier_cs_7/examples/gemini3pro_3.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Structure to represent an edge in the DAG
struct Edge {
    int to;
    int w;
};

// Adjacency list to store the graph. Max nodes 100.
vector<Edge> adj[105];
int node_cnt = 0;
int H[25]; // H[k] stores the node index that is the root of a full binary DAG of height k

// Function to allocate a new node
int new_node() {
    return ++node_cnt;
}

// Function to add a directed edge
void add_edge(int u, int v, int w) {
    adj[u].push_back({v, w});
}

// Lazily retrieve (or create) the node H[k]
// H[k] is the root of a DAG that generates all binary strings of length k.
// H[0] is the Sink node.
int get_H(int k) {
    if (H[k] != 0) return H[k];
    
    // Create new node for H[k]
    int u = new_node();
    H[k] = u;
    // Recursively ensure H[k-1] exists
    int target = get_H(k - 1);
    // Connect H[k] to H[k-1] with both 0 and 1
    add_edge(u, target, 0);
    add_edge(u, target, 1);
    return u;
}

// Construct a path/DAG for values >= val (suffix logic)
// 'u' is the current node
// 'bit' is the current bit index we are deciding (from MSB downwards)
// 'val' is the lower bound value
void add_chain_lower(int u, int bit, int val) {
    if (bit < 0) return;
    int bit_val = (val >> bit) & 1;
    
    if (bit_val == 1) {
        // We are constrained to 1. The '0' path would be less than val (invalid).
        if (bit == 0) {
            add_edge(u, H[0], 1);
        } else {
            int next_node = new_node();
            add_edge(u, next_node, 1);
            add_chain_lower(next_node, bit - 1, val);
        }
    } else {
        // bit_val is 0.
        // We can go '0', continuing the constraint.
        if (bit == 0) {
            add_edge(u, H[0], 0);
        } else {
            int next_tight = new_node();
            add_edge(u, next_tight, 0);
            add_chain_lower(next_tight, bit - 1, val);
        }
        // We can also go '1'. Since 1 > 0, all subsequent bits are free.
        // The remaining length is 'bit'. Target is H[bit].
        add_edge(u, get_H(bit), 1);
    }
}

// Construct a path/DAG for values <= val (suffix logic)
void add_chain_upper(int u, int bit, int val) {
    if (bit < 0) return;
    int bit_val = (val >> bit) & 1;
    
    if (bit_val == 0) {
        // Constrained to 0.
        if (bit == 0) {
            add_edge(u, H[0], 0);
        } else {
            int next_node = new_node();
            add_edge(u, next_node, 0);
            add_chain_upper(next_node, bit - 1, val);
        }
    } else {
        // bit_val is 1.
        // Can go '1' (constrained).
        if (bit == 0) {
            add_edge(u, H[0], 1);
        } else {
            int next_tight = new_node();
            add_edge(u, next_tight, 1);
            add_chain_upper(next_tight, bit - 1, val);
        }
        // Can go '0' (loose). Since 0 < 1, subsequent bits free.
        add_edge(u, get_H(bit), 0);
    }
}

// Construct DAG for range [L, R] with fixed length
void add_chain_between(int u, int bit, int L, int R) {
    if (bit < 0) return;
    int L_bit = (L >> bit) & 1;
    int R_bit = (R >> bit) & 1;

    if (L_bit == R_bit) {
        // Common prefix
        if (bit == 0) {
            add_edge(u, H[0], L_bit);
        } else {
            int next_node = new_node();
            add_edge(u, next_node, L_bit);
            add_chain_between(next_node, bit - 1, L, R);
        }
    } else {
        // Divergence point. L must be 0, R must be 1.
        
        // Lower branch: choose 0. Constraints come from L (lower bound).
        if (bit == 0) {
            add_edge(u, H[0], 0);
        } else {
            int v0 = new_node();
            add_edge(u, v0, 0);
            add_chain_lower(v0, bit - 1, L);
        }

        // Upper branch: choose 1. Constraints come from R (upper bound).
        if (bit == 0) {
            add_edge(u, H[0], 1);
        } else {
            int v1 = new_node();
            add_edge(u, v1, 1);
            add_chain_upper(v1, bit - 1, R);
        }
    }
}

// Calculate number of bits required to represent n
int get_len(int n) {
    if (n == 0) return 0;
    return 32 - __builtin_clz(n);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int L, R;
    if (!(cin >> L >> R)) return 0;

    int Source = new_node(); // Node 1 is Source
    int Sink = new_node();   // Node 2 is Sink
    H[0] = Sink;

    int lenL = get_len(L);
    int lenR = get_len(R);

    // Because we cannot have leading zeros, the MSB for any number in [L, R] is 1.
    // We handle the MSB explicitly by creating an edge '1' from Source.
    // The recursive functions handle bits from len-2 down to 0.

    if (lenL == lenR) {
        // All numbers have the same bit length
        if (lenL == 1) {
            // Range [1, 1]
            add_edge(Source, Sink, 1);
        } else {
            int v = new_node();
            add_edge(Source, v, 1);
            add_chain_between(v, lenL - 2, L, R);
        }
    } else {
        // Numbers have different lengths. We process each length group.
        
        // 1. Numbers of length lenL: Range [L, 2^lenL - 1]
        if (lenL == 1) {
            add_edge(Source, Sink, 1);
        } else {
            int vL = new_node();
            add_edge(Source, vL, 1);
            add_chain_lower(vL, lenL - 2, L);
        }
        
        // 2. Numbers of intermediate lengths: Range [2^(k-1), 2^k - 1] for k in (lenL, lenR)
        // These are full ranges of length k. Corresponds to '1' followed by any k-1 bits.
        for (int k = lenL + 1; k < lenR; ++k) {
            // Edge '1' leads to H[k-1] which generates all strings of length k-1
            add_edge(Source, get_H(k - 1), 1);
        }
        
        // 3. Numbers of length lenR: Range [2^(lenR-1), R]
        if (lenR > 1) {
            int vR = new_node();
            add_edge(Source, vR, 1);
            add_chain_upper(vR, lenR - 2, R);
        }
    }

    // Output graph
    cout << node_cnt << "\n";
    for (int i = 1; i <= node_cnt; ++i) {
        cout << adj[i].size();
        for (auto& e : adj[i]) {
            cout << " " << e.to << " " << e.w;
        }
        cout << "\n";
    }

    return 0;
}