QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#744458 | #9519. Build a Computer | kikcer | AC ✓ | 0ms | 3836kb | C++20 | 7.1kb | 2024-11-13 21:59:05 | 2024-11-13 21:59:10 |
Judging History
answer
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <bitset>
#include <map>
#include <fstream>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <unordered_set>
#include <set>
#include <queue>
#define rg register
#define LL long long
#define all(a) a.begin() + 1, a.end()
#define i64 long long
#define ll long long
#define fo(a, b, c) for (int a = b; a <= c; ++a)
#define PII pair<int, int>
#define tI3 tuple<int, int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define tI4 tuple<int, int, int, int>
const ll prime1 = 10000000343, prime2 = 10000000601, prime3 = 1000000000000357, prime4 = 1000000000001269, prime5 = 1000000000000000079, prime6 = 1000000000000000031;
using namespace std;
ll l, r;
string L, R;
void solve()
{
cin >> l >> r;
ll tmp = l;
while (tmp)
{
L += (tmp % 2) + '0';
tmp /= 2;
}
reverse(L.begin(), L.end());
cerr << L << endl;
tmp = r;
while (tmp)
{
R += (tmp % 2) + '0';
tmp /= 2;
}
reverse(R.begin(), R.end());
cerr << R << endl;
vector<vector<pair<int, int>>> e(110);
int n = L.size(), m = R.size();
if (n != m)
{
int S = 1, T = 2;
int p = 0;
while (p < n && L[p] != '0')
p++;
int q = 1;
while (q < m && R[q] != '1')
q++;
int siz = max(n - p - 1, m - q - 1);
if (n + 1 < m)
siz = max(siz, m - 2);
int pos = T;
int cur = T;
for (int i = 1; i <= siz; i++)
{
if (i < siz)
{
e[++cur].push_back({cur + 1, 1});
e[cur].push_back({cur + 1, 0});
}
else
{
e[++cur].push_back({T, 1});
e[cur].push_back({T, 0});
}
}
pos = cur;
int las = S;
for (int i = 0; i < L.size(); i++)
{
if (i == L.size() - 1)
{
e[las].push_back({T, 1});
if (L[i] == '0')
e[las].push_back({T, 0});
break;
}
e[las].push_back({++cur, L[i] - '0'});
if (L[i] == '0')
e[las].push_back({pos - (L.size() - i - 2), 1});
las = cur;
}
for (int i = L.size() + 1; i < R.size(); i++)
{
e[S].push_back({pos - (i - 2), 1});
}
las = S;
for (int i = 0; i < R.size(); i++)
{
if (i == R.size() - 1)
{
e[las].push_back({T, 0});
if (R[i] == '1')
e[las].push_back({T, 1});
break;
}
e[las].push_back({++cur, R[i] - '0'});
if (i > 0 && R[i] == '1')
e[las].push_back({pos - (R.size() - i - 2), 0});
las = cur;
}
cout << cur << '\n';
for (int i = 1; i <= cur; i++)
{
cout << e[i].size() << ' ';
for (auto [v, w] : e[i])
cout << v << ' ' << w << ' ';
cout << '\n';
}
}
else
{
int S = 1, T = 2;
int cur = 2;
int id = 0;
int las = S;
while (id < L.size() && L[id] == R[id])
{
if (id == L.size() - 1)
{
e[las].push_back({T, L[id] - '0'});
id++;
break;
}
e[las].push_back({++cur, L[id] - '0'});
las = cur;
id++;
}
cerr << id << ' ' << L.size() << endl;
if (id == L.size())
{
// cout << L.size() << ' ' << cur;
cout << cur << '\n';
for (int i = 1; i <= cur; i++)
{
cout << e[i].size() << ' ';
for (auto [v, w] : e[i])
cout << v << ' ' << w << ' ';
cout << '\n';
}
return;
}
else if (id == L.size() - 1)
{
e[las].push_back({T, 0});
e[las].push_back({T, 1});
cout << cur << '\n';
for (int i = 1; i <= cur; i++)
{
cout << e[i].size() << ' ';
for (auto [v, w] : e[i])
cout << v << ' ' << w << ' ';
cout << '\n';
}
return;
}
int cnt = cur;
int tmp = las;
int pos = id;
// cerr << cur << endl;
for (int i = id + 1; i < L.size() - 1; i++)
{
if (L[i] == '0' || R[i] == '1')
{
las = ++cur;
for (int j = i; j < L.size() - 1; j++)
{
if (j == L.size() - 2)
{
e[las].push_back({T, 1});
e[las].push_back({T, 0});
break;
}
else
{
e[las].push_back({++cur, 1});
e[las].push_back({cur, 0});
}
las = cur;
}
pos = i;
break;
}
}
cerr << tmp << endl;
las = tmp;
e[las].push_back({++cur, 0});
las = cur;
for (int i = id + 1; i < L.size(); i++)
{
if (i == L.size() - 1)
{
e[las].push_back({T, 1});
if (L[i] == '0')
e[las].push_back({T, 0});
}
else
{
e[las].push_back({++cur, L[i] - '0'});
if (L[i] == '0')
e[las].push_back({cnt + i - pos + 1, 1});
}
las = cur;
}
// cerr << cur << endl;
las = tmp;
e[las].push_back({++cur, 1});
las = cur;
for (int i = id + 1; i < L.size(); i++)
{
if (i == L.size() - 1)
{
e[las].push_back({T, 0});
if (R[i] == '1')
e[las].push_back({T, 1});
}
else
{
e[las].push_back({++cur, R[i] - '0'});
if (R[i] == '1')
e[las].push_back({cnt + i - pos + 1, 0});
}
las = cur;
}
// cout << L.size() << ' ' << id << ' ' << cur << '\n';
cout << cur << '\n';
for (int i = 1; i <= cur; i++)
{
cout << e[i].size() << ' ';
for (auto [v, w] : e[i])
cout << v << ' ' << w << ' ';
cout << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
5 7
output:
5 1 3 1 0 2 4 0 5 1 1 2 1 2 2 0 2 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
10 27
output:
12 2 6 1 9 1 0 2 4 1 4 0 2 5 1 5 0 2 2 1 2 0 2 7 0 4 1 1 8 1 2 2 1 2 0 2 10 1 3 0 1 11 0 2 12 1 5 0 2 2 0 2 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
5 13
output:
9 2 5 1 7 1 0 2 4 1 4 0 2 2 1 2 0 2 6 0 4 1 1 2 1 2 8 1 3 0 1 9 0 2 2 0 2 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 1000000
output:
39 20 2 1 20 1 19 1 18 1 17 1 16 1 15 1 14 1 13 1 12 1 11 1 10 1 9 1 8 1 7 1 6 1 5 1 4 1 3 1 21 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 19 1 19 0 2 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
7 9
output:
7 2 3 1 5 1 0 1 4 1 1 2 1 1 6 0 1 7 0 2 2 0 2 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 7
output:
6 2 4 1 5 1 0 2 2 1 2 0 1 2 1 2 6 1 3 0 2 2 0 2 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
1 5
output:
5 3 2 1 3 1 4 1 0 2 2 1 2 0 1 5 0 2 2 0 2 1
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 4
output:
5 3 2 1 3 1 4 1 0 2 2 1 2 0 1 5 0 1 2 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
8 9
output:
5 1 3 1 0 1 4 0 1 5 0 2 2 0 2 1
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
7 51
output:
13 4 7 1 4 1 3 1 9 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 2 1 2 0 1 8 1 1 2 1 2 10 1 3 0 1 11 0 1 12 0 2 13 1 6 0 2 2 0 2 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
51 79
output:
16 2 6 1 11 1 0 2 4 1 4 0 2 5 1 5 0 2 2 1 2 0 1 7 1 2 8 0 3 1 2 9 0 4 1 1 10 1 1 2 1 1 12 0 1 13 0 2 14 1 3 0 2 15 1 4 0 2 16 1 5 0 2 2 0 2 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
92 99
output:
14 1 3 1 0 2 5 0 10 1 2 2 1 2 0 1 6 1 1 7 1 1 8 1 2 9 0 4 1 2 2 1 2 0 1 11 0 1 12 0 1 13 0 2 14 1 4 0 2 2 0 2 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
27 36
output:
13 2 5 1 9 1 0 2 4 1 4 0 2 2 1 2 0 1 6 1 2 7 0 3 1 1 8 1 1 2 1 1 10 0 1 11 0 2 12 1 3 0 1 13 0 1 2 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
55 84
output:
17 2 7 1 12 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 2 1 2 0 1 8 1 2 9 0 4 1 1 10 1 1 11 1 1 2 1 1 13 0 2 14 1 3 0 1 15 0 2 16 1 5 0 1 17 0 1 2 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
297208 929600
output:
57 2 21 1 39 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 19 1 19 0 2 20 1 20 0 2 2 1 2 0 2 22 0 4 1 2 23 0 5 1 1 24 1 2 25 0 7 1 2 26 0 8 1 2 27 ...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
45728 589156
output:
54 5 21 1 5 1 4 1 3 1 36 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 19 1 19 0 2 20 1 20 0 2 2 1 2 0 2 22 0 7 1 1 23 1 1 24 1 2 25 0 10 1 2 26 0 1...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
129152 138000
output:
47 2 15 1 31 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 2 1 2 0 1 16 1 1 17 1 1 18 1 1 19 1 1 20 1 2 21 0 5 1 2 22 0 6 1 2 23 0 7 1 1 24 1 2 25 0 9 1 2 26 0 10 1 2 27 0 11 1 2 28 0 12 1 2 29...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
245280 654141
output:
56 3 21 1 3 1 38 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 19 1 19 0 2 20 1 20 0 2 2 1 2 0 1 22 1 1 23 1 2 24 0 7 1 1 25 1 1 26 1 1 27 1 1 28 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
202985 296000
output:
52 2 18 1 35 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 2 1 2 0 1 19 1 2 20 0 3 1 2 21 0 4 1 2 22 0 5 1 1 23 1 1 24 1 2 25 0 8 1 2 26 0 9 1 2 27 0 10 1 1 2...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
438671 951305
output:
57 2 21 1 39 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 19 1 19 0 2 20 1 20 0 2 2 1 2 0 1 22 1 2 23 0 5 1 1 24 1 2 25 0 7 1 1 26 1 1 27 1 2 28 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
425249 739633
output:
56 2 20 1 38 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 19 1 19 0 2 2 1 2 0 1 21 1 2 22 0 4 1 2 23 0 5 1 1 24 1 1 25 1 1 26 1 1 27 1 1 28 1 2 ...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
551207 961718
output:
56 1 3 1 0 2 21 0 39 1 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 19 1 19 0 2 20 1 20 0 2 2 1 2 0 2 22 0 4 1 2 23 0 5 1 2 24 0 6 1 1 25 1 1 26 1 2 27 0 9 1 1...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
114691 598186
output:
55 4 21 1 4 1 3 1 37 1 0 2 4 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 19 1 19 0 2 20 1 20 0 2 2 1 2 0 1 22 1 1 23 1 2 24 0 8 1 2 25 0 9 1 2 26 0 10 1 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
234654 253129
output:
46 1 3 1 0 1 4 1 1 5 1 2 19 0 33 1 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 2 1 2 0 2 20 0 6 1 1 21 1 2 22 0 8 1 1 23 1 2 24 0 10 1 2 25 0 11 1 1 26 1 2 27 0 13 1 2 28 0 14 1 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
554090 608599
output:
52 1 3 1 0 1 4 0 1 5 0 2 21 0 37 1 2 7 1 7 0 2 8 1 8 0 2 9 1 9 0 2 10 1 10 0 2 11 1 11 0 2 12 1 12 0 2 13 1 13 0 2 14 1 14 0 2 15 1 15 0 2 16 1 16 0 2 17 1 17 0 2 18 1 18 0 2 19 1 19 0 2 20 1 20 0 2 2 1 2 0 2 22 0 6 1 1 23 1 1 24 1 1 25 1 2 26 0 10 1 1 27 1 2 28 0 12 1 2 2...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed