Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup
File size: 3,774 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
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int w;
};

struct Builder {
    vector<vector<Edge>> adj;          // 1-indexed
    int start = -1, terminal = -1;
    vector<int> fullMemo;              // fullMemo[rem] -> node id (rem bits remaining)
    unordered_map<long long, int> memo; // (rem,a,b) -> node id

    int newNode() {
        adj.push_back({});
        return (int)adj.size() - 1;
    }

    int fullNode(int rem) {
        if (fullMemo[rem] != -1) return fullMemo[rem];
        int id = newNode();
        fullMemo[rem] = id;
        int child = fullNode(rem - 1);
        adj[id].push_back({child, 0});
        adj[id].push_back({child, 1});
        return id;
    }

    int buildRange(int a, int b, int rem) {
        if (rem == 0) return terminal;
        if (a == 0 && b == ((1 << rem) - 1)) return fullNode(rem);

        long long key = ( (long long)rem << 40 ) | ( (long long)a << 20 ) | (long long)b;
        auto it = memo.find(key);
        if (it != memo.end()) return it->second;

        int id = newNode();
        memo[key] = id;

        int half = 1 << (rem - 1);
        int msbA = (a >= half) ? 1 : 0;
        int msbB = (b >= half) ? 1 : 0;

        if (msbA == msbB) {
            int bit = msbA;
            int na = a - bit * half;
            int nb = b - bit * half;
            int child = buildRange(na, nb, rem - 1);
            adj[id].push_back({child, bit});
        } else {
            int child0 = buildRange(a, half - 1, rem - 1);
            int child1 = buildRange(0, b - half, rem - 1);
            adj[id].push_back({child0, 0});
            adj[id].push_back({child1, 1});
        }

        return id;
    }
};

static int bitlen(int x) {
    return 32 - __builtin_clz((unsigned)x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, R;
    cin >> L >> R;

    int lenMax = bitlen(R);
    int maxRem = lenMax - 1;

    Builder B;
    B.adj.reserve(128);
    B.adj.push_back({});          // dummy 0
    B.start = B.newNode();        // 1
    B.terminal = B.newNode();     // 2

    B.fullMemo.assign(maxRem + 1, -1);
    B.fullMemo[0] = B.terminal;

    B.memo.reserve(2048);
    B.memo.max_load_factor(0.7f);

    vector<long long> pow2(lenMax + 1);
    pow2[0] = 1;
    for (int i = 1; i <= lenMax; i++) pow2[i] = pow2[i - 1] << 1;

    for (int len = 1; len <= lenMax; len++) {
        long long minVal = pow2[len - 1];
        long long maxVal = pow2[len] - 1;
        long long lo = max<long long>(L, minVal);
        long long hi = min<long long>(R, maxVal);
        if (lo > hi) continue;

        int rem = len - 1;
        int entry;
        if (lo == minVal && hi == maxVal) {
            entry = B.fullNode(rem);
        } else {
            int a = (int)(lo - minVal);
            int b = (int)(hi - minVal);
            entry = (rem == 0) ? B.terminal : B.buildRange(a, b, rem);
        }
        B.adj[B.start].push_back({entry, 1});
    }

    int n = (int)B.adj.size() - 1;

    // Sanity: ensure exactly one node with indegree 0 (start)
    // and exactly one node with outdegree 0 (terminal).
    // (Not strictly necessary to print, but ensures construction is sound.)
    vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        outdeg[i] = (int)B.adj[i].size();
        for (auto &e : B.adj[i]) indeg[e.to]++;
    }
    // If there are any nodes other than start with indegree 0, they are unreachable/unreferenced.
    // This construction should not create such nodes.

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

    return 0;
}