QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686402 | #9519. Build a Computer | SGColin# | AC ✓ | 2ms | 7856kb | C++20 | 3.9kb | 2024-10-29 12:09:50 | 2024-10-29 12:09:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
const int N = 1000007;
int lg[N], id[101];
vector<pii> e[101];
int main() {
lg[0] = lg[1] = 0;
rep(i, 2, N - 1) lg[i] = lg[i >> 1] + 1;
int L = rd(), R = rd();
int S = 1, T = 2, tot = 2, mx = -1;
auto print = [&]() {
per(i, mx, 0) id[i] = ++tot;
per(i, mx, 1) {e[id[i]].eb(id[i - 1], 0); e[id[i]].eb(id[i - 1], 1);}
e[id[0]].eb(T, 0); e[id[0]].eb(T, 1);
printf("%d\n", tot);
rep(u, 1, tot) {
printf("%d", (int)e[u].size());
for (auto [v, w] : e[u]) printf(" %d %d", (v <= 0 ? id[-v] : v), w);
puts("");
}
};
if (L == R) { // chain
per(i, lg[L], 1) {
e[S].eb(++tot, ((L >> i) & 1));
S = tot;
}
e[S].eb(T, (L & 1));
print(); return 0;
}
if (L == 1) {
e[S].eb(T, 1);
per(i, lg[R] - 2, 0) e[S].eb(-i, 1); mx = max(mx, lg[R] - 2);
int SR = ++tot; e[S].eb(SR, 1);
per(i, lg[R] - 1, 1) { // upper bound
if ((R >> i) & 1) {
e[SR].eb(1 - i, 0); mx = max(mx, i - 1);
e[SR].eb(++tot, 1); SR = tot;
} else {
e[SR].eb(++tot, 0); SR = tot;
}
}
e[SR].eb(T, 0);
if (R & 1) e[SR].eb(T, 1);
print(); return 0;
}
if (lg[L] == lg[R]) {
int nw = lg[L];
while (((L >> nw) & 1) == ((R >> nw) & 1)) {
e[S].eb(++tot, ((L >> nw) & 1));
S = tot; --nw;
}
if (nw == 0) {
e[S].eb(T, 0);
e[S].eb(T, 1);
print(); return 0;
}
int SR = ++tot; e[S].eb(SR, 1);
per(i, nw - 1, 1) { // upper bound
if ((R >> i) & 1) {
e[SR].eb(1 - i, 0); mx = max(mx, i - 1);
e[SR].eb(++tot, 1); SR = tot;
} else {
e[SR].eb(++tot, 0); SR = tot;
}
}
e[SR].eb(T, 0);
if (R & 1) e[SR].eb(T, 1);
int SL = ++tot; e[S].eb(SL, 0);
per(i, nw - 1, 1) { // lower bound
if ((L >> i) & 1) {
e[SL].eb(++tot, 1); SL = tot;
} else {
e[SL].eb(1 - i, 1); mx = max(mx, i - 1);
e[SL].eb(++tot, 0); SL = tot;
}
}
e[SL].eb(T, 1);
if (!(L & 1)) e[SL].eb(T, 0);
} else {
per(i, lg[R] - 2, lg[L]) e[S].eb(-i, 1);
if (lg[R] - 2 >= lg[L]) mx = max(mx, lg[R] - 2);
int SR = ++tot; e[S].eb(SR, 1);
per(i, lg[R] - 1, 1) { // upper bound
if ((R >> i) & 1) {
e[SR].eb(1 - i, 0); mx = max(mx, i - 1);
e[SR].eb(++tot, 1); SR = tot;
} else {
e[SR].eb(++tot, 0); SR = tot;
}
}
e[SR].eb(T, 0);
if (R & 1) e[SR].eb(T, 1);
int SL = ++tot; e[S].eb(SL, 1);
per(i, lg[L] - 1, 1) { // lower bound
if ((L >> i) & 1) {
e[SL].eb(++tot, 1); SL = tot;
} else {
e[SL].eb(1 - i, 1); mx = max(mx, i - 1);
e[SL].eb(++tot, 0); SL = tot;
}
}
e[SL].eb(T, 1);
if (!(L & 1)) e[SL].eb(T, 0);
}
print();
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7668kb
input:
5 7
output:
5 1 3 1 0 2 4 1 5 0 2 2 0 2 1 1 2 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 7724kb
input:
10 27
output:
12 2 3 1 7 1 0 2 10 0 4 1 1 5 0 2 12 0 6 1 2 2 0 2 1 2 11 1 8 0 1 9 1 2 2 1 2 0 2 11 0 11 1 2 12 0 12 1 2 2 0 2 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 7672kb
input:
5 13
output:
9 2 3 1 6 1 0 2 8 0 4 1 1 5 0 2 2 0 2 1 2 9 1 7 0 1 2 1 2 9 0 9 1 2 2 0 2 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 2ms
memory: 7856kb
input:
1 1000000
output:
39 20 2 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 3 1 0 2 22 0 4 1 2 23 0 5 1 2 24 0 6 1 1 7 0 2 26 0 8 1 1 9 0 1 10 0 1 11 0 1 12 0 2 31 0 13 1 1 14 0 1 15 0 2 34 0 16 1 1 17 0 1 18 0 1 19 0 1 20 0 1 21 0 1 2 0 2 23 0 23 1 2 24 0 24 1 2 25 0 25 1 2 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 2ms
memory: 7648kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 2ms
memory: 7788kb
input:
7 9
output:
7 2 3 1 6 1 0 1 4 0 1 5 0 2 2 0 2 1 1 7 1 1 2 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 2ms
memory: 7720kb
input:
3 7
output:
6 2 3 1 5 1 0 2 6 0 4 1 2 2 0 2 1 1 2 1 2 2 0 2 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 2ms
memory: 7716kb
input:
1 5
output:
5 3 2 1 5 1 3 1 0 1 4 0 2 2 0 2 1 2 2 0 2 1
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 7720kb
input:
1 4
output:
5 3 2 1 5 1 3 1 0 1 4 0 1 2 0 2 2 0 2 1
result:
ok ok
Test #10:
score: 0
Accepted
time: 2ms
memory: 7724kb
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: 7724kb
input:
7 51
output:
13 4 10 1 11 1 3 1 8 1 0 2 10 0 4 1 1 5 0 1 6 0 2 13 0 7 1 2 2 0 2 1 1 9 1 1 2 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 2 0 2 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 2ms
memory: 7708kb
input:
51 79
output:
16 2 3 1 9 1 0 1 4 0 1 5 0 2 14 0 6 1 2 15 0 7 1 2 16 0 8 1 2 2 0 2 1 1 10 1 2 14 1 11 0 2 15 1 12 0 1 13 1 1 2 1 2 15 0 15 1 2 16 0 16 1 2 2 0 2 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 2ms
memory: 7672kb
input:
92 99
output:
14 1 3 1 0 2 4 1 9 0 1 5 0 1 6 0 1 7 0 2 14 0 8 1 2 2 0 2 1 1 10 1 1 11 1 1 12 1 2 14 1 13 0 2 2 1 2 0 2 2 0 2 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 2ms
memory: 7704kb
input:
27 36
output:
13 2 3 1 8 1 0 1 4 0 1 5 0 2 12 0 6 1 1 7 0 1 2 0 1 9 1 2 12 1 10 0 1 11 1 1 2 1 2 13 0 13 1 2 2 0 2 1
result:
ok ok
Test #15:
score: 0
Accepted
time: 2ms
memory: 7720kb
input:
55 84
output:
17 2 3 1 9 1 0 1 4 0 2 14 0 5 1 1 6 0 2 16 0 7 1 1 8 0 1 2 0 1 10 1 2 15 1 11 0 1 12 1 1 13 1 1 2 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 2 0 2 1
result:
ok ok
Test #16:
score: 0
Accepted
time: 2ms
memory: 7708kb
input:
297208 929600
output:
57 2 3 1 22 1 0 2 40 0 4 1 2 41 0 5 1 1 6 0 1 7 0 1 8 0 2 45 0 9 1 1 10 0 2 47 0 11 1 2 48 0 12 1 2 49 0 13 1 2 50 0 14 1 1 15 0 2 52 0 16 1 1 17 0 1 18 0 1 19 0 1 20 0 1 21 0 1 2 0 2 41 1 23 0 2 42 1 24 0 1 25 1 2 44 1 26 0 2 45 1 27 0 2 46 1 28 0 1 29 1 2 48 1 30 0 2 49 1 31 0 2 50 1 32 0 1 33 1 1...
result:
ok ok
Test #17:
score: 0
Accepted
time: 2ms
memory: 7716kb
input:
45728 589156
output:
54 5 37 1 38 1 39 1 3 1 22 1 0 1 4 0 1 5 0 1 6 0 2 40 0 7 1 2 41 0 8 1 2 42 0 9 1 2 43 0 10 1 2 44 0 11 1 2 45 0 12 1 1 13 0 2 47 0 14 1 1 15 0 2 49 0 16 1 2 50 0 17 1 1 18 0 1 19 0 2 53 0 20 1 1 21 0 1 2 0 2 41 1 23 0 1 24 1 1 25 1 2 44 1 26 0 2 45 1 27 0 1 28 1 2 47 1 29 0 1 30 1 2 49 1 31 0 1 32 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 2ms
memory: 7672kb
input:
129152 138000
output:
47 2 3 1 20 1 0 1 4 0 1 5 0 1 6 0 1 7 0 2 36 0 8 1 2 37 0 9 1 1 10 0 2 39 0 11 1 2 40 0 12 1 1 13 0 1 14 0 1 15 0 2 44 0 16 1 1 17 0 1 18 0 1 19 0 1 2 0 1 21 1 1 22 1 1 23 1 1 24 1 1 25 1 2 38 1 26 0 2 39 1 27 0 2 40 1 28 0 1 29 1 2 42 1 30 0 2 43 1 31 0 2 44 1 32 0 2 45 1 33 0 2 46 1 34 0 2 47 1 35...
result:
ok ok
Test #19:
score: 0
Accepted
time: 2ms
memory: 7724kb
input:
245280 654141
output:
56 3 39 1 3 1 22 1 0 1 4 0 1 5 0 2 41 0 6 1 2 42 0 7 1 2 43 0 8 1 2 44 0 9 1 2 45 0 10 1 2 46 0 11 1 1 12 0 2 48 0 13 1 2 49 0 14 1 1 15 0 1 16 0 2 52 0 17 1 2 53 0 18 1 2 54 0 19 1 2 55 0 20 1 1 21 0 2 2 0 2 1 1 23 1 1 24 1 2 43 1 25 0 1 26 1 1 27 1 1 28 1 1 29 1 1 30 1 2 49 1 31 0 2 50 1 32 0 2 51...
result:
ok ok
Test #20:
score: 0
Accepted
time: 2ms
memory: 7796kb
input:
202985 296000
output:
52 2 3 1 21 1 0 1 4 0 1 5 0 2 38 0 6 1 1 7 0 1 8 0 1 9 0 1 10 0 2 43 0 11 1 1 12 0 1 13 0 1 14 0 2 47 0 15 1 1 16 0 1 17 0 1 18 0 1 19 0 1 20 0 1 2 0 1 22 1 2 38 1 23 0 2 39 1 24 0 2 40 1 25 0 1 26 1 1 27 1 2 43 1 28 0 2 44 1 29 0 2 45 1 30 0 1 31 1 1 32 1 1 33 1 2 49 1 34 0 1 35 1 2 51 1 36 0 2 52 ...
result:
ok ok
Test #21:
score: 0
Accepted
time: 2ms
memory: 7668kb
input:
438671 951305
output:
57 2 3 1 22 1 0 2 40 0 4 1 2 41 0 5 1 1 6 0 2 43 0 7 1 1 8 0 1 9 0 1 10 0 1 11 0 2 48 0 12 1 1 13 0 1 14 0 1 15 0 1 16 0 1 17 0 1 18 0 2 55 0 19 1 1 20 0 1 21 0 2 2 0 2 1 1 23 1 2 42 1 24 0 1 25 1 2 44 1 26 0 1 27 1 1 28 1 2 47 1 29 0 2 48 1 30 0 2 49 1 31 0 1 32 1 1 33 1 2 52 1 34 0 2 53 1 35 0 2 5...
result:
ok ok
Test #22:
score: 0
Accepted
time: 2ms
memory: 7720kb
input:
425249 739633
output:
56 2 3 1 22 1 0 1 4 0 2 40 0 5 1 2 41 0 6 1 1 7 0 2 43 0 8 1 1 9 0 1 10 0 2 46 0 11 1 1 12 0 1 13 0 2 49 0 14 1 1 15 0 1 16 0 2 52 0 17 1 2 53 0 18 1 1 19 0 1 20 0 1 21 0 2 2 0 2 1 1 23 1 2 41 1 24 0 2 42 1 25 0 1 26 1 1 27 1 1 28 1 1 29 1 1 30 1 2 48 1 31 0 1 32 1 2 50 1 33 0 2 51 1 34 0 1 35 1 2 5...
result:
ok ok
Test #23:
score: 0
Accepted
time: 2ms
memory: 7668kb
input:
551207 961718
output:
56 1 3 1 0 2 4 1 22 0 2 40 0 5 1 1 6 0 2 42 0 7 1 1 8 0 2 44 0 9 1 1 10 0 2 46 0 11 1 2 47 0 12 1 1 13 0 1 14 0 2 50 0 15 1 1 16 0 2 52 0 17 1 2 53 0 18 1 1 19 0 2 55 0 20 1 2 56 0 21 1 1 2 0 2 40 1 23 0 2 41 1 24 0 2 42 1 25 0 1 26 1 1 27 1 2 45 1 28 0 1 29 1 2 47 1 30 0 2 48 1 31 0 1 32 1 2 50 1 3...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 7796kb
input:
114691 598186
output:
55 4 38 1 39 1 3 1 22 1 0 1 4 0 1 5 0 2 40 0 6 1 1 7 0 1 8 0 2 43 0 9 1 1 10 0 1 11 0 1 12 0 1 13 0 1 14 0 2 49 0 15 1 1 16 0 2 51 0 17 1 1 18 0 2 53 0 19 1 1 20 0 2 55 0 21 1 1 2 0 1 23 1 1 24 1 2 43 1 25 0 2 44 1 26 0 2 45 1 27 0 2 46 1 28 0 2 47 1 29 0 2 48 1 30 0 2 49 1 31 0 2 50 1 32 0 2 51 1 3...
result:
ok ok
Test #25:
score: 0
Accepted
time: 2ms
memory: 7668kb
input:
234654 253129
output:
46 1 3 1 0 1 4 1 1 5 1 2 6 1 20 0 1 7 0 2 35 0 8 1 2 36 0 9 1 2 37 0 10 1 1 11 0 1 12 0 2 40 0 13 1 2 41 0 14 1 1 15 0 1 16 0 2 44 0 17 1 1 18 0 1 19 0 2 2 0 2 1 2 34 1 21 0 1 22 1 2 36 1 23 0 1 24 1 2 38 1 25 0 2 39 1 26 0 1 27 1 2 41 1 28 0 2 42 1 29 0 1 30 1 1 31 1 1 32 1 1 33 1 2 2 1 2 0 2 35 0 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 2ms
memory: 7792kb
input:
554090 608599
output:
52 1 3 1 0 1 4 0 1 5 0 2 6 1 22 0 1 7 0 2 39 0 8 1 1 9 0 1 10 0 2 42 0 11 1 1 12 0 1 13 0 2 45 0 14 1 1 15 0 2 47 0 16 1 1 17 0 2 49 0 18 1 1 19 0 2 51 0 20 1 2 52 0 21 1 2 2 0 2 1 2 38 1 23 0 1 24 1 1 25 1 1 26 1 2 42 1 27 0 1 28 1 2 44 1 29 0 2 45 1 30 0 2 46 1 31 0 1 32 1 1 33 1 2 49 1 34 0 1 35 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed