QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#678232 | #9519. Build a Computer | ucup-team987# | AC ✓ | 0ms | 3820kb | C++20 | 4.0kb | 2024-10-26 14:22:42 | 2024-10-26 14:22:43 |
Judging History
answer
#if __INCLUDE_LEVEL__ == 0
#include __BASE_FILE__
void Solve() {
int L, R;
IN(L, R);
vector<tuple<int, int, int>> edges;
for (int i : Rep(80, 100)) {
edges.emplace_back(i, i + 1, 0);
edges.emplace_back(i, i + 1, 1);
}
int nxt = 1;
for (int k : Rep1(1, 20)) {
int l = max(L, 1 << (k - 1));
int r = min(R, (1 << k) - 1);
if (r < l) {
continue;
}
if (r - l + 1 == 1 << (k - 1)) {
edges.emplace_back(0, 100 - k + 1, 1);
continue;
}
string s(k, '0');
string t(k, '0');
for (int i : Rep(0, k)) {
if (l >> (k - i - 1) & 1) {
s[i] = '1';
}
if (r >> (k - i - 1) & 1) {
t[i] = '1';
}
}
int pl = 0, pr = 0;
bool same = true;
for (int i : Rep(0, k)) {
if (s[i] < t[i]) {
same = false;
}
int nl, nr;
if (i + 1 == k) {
nl = nr = 100;
} else if (same) {
nl = nr = nxt++;
} else {
nl = nxt++;
nr = nxt++;
}
if (same) {
edges.emplace_back(pl, nl, s[i] - '0');
} else {
edges.emplace_back(pl, nl, s[i] - '0');
edges.emplace_back(pr, nr, t[i] - '0');
if (pl != pr && s[i] == '0') {
edges.emplace_back(pl, 100 - (k - i - 1), 1);
}
if (pl != pr && t[i] == '1') {
edges.emplace_back(pr, 100 - (k - i - 1), 0);
}
}
pl = nl;
pr = nr;
}
}
vector<bool> need(101, true);
{
vector<vector<int>> g(101);
for (auto [i, j, x] : edges) {
g[i].push_back(j);
}
vector<bool> f(101);
f[0] = 1;
for (int i : Rep(0, 100)) {
if (f[i]) {
for (int j : g[i]) {
f[j] = true;
}
}
}
for (int i : Rep1(0, 100)) {
if (!f[i]) {
need[i] = false;
}
}
}
{
vector<vector<int>> g(101);
for (auto [i, j, x] : edges) {
g[j].push_back(i);
}
vector<bool> f(101);
f[100] = 1;
for (int i : Rev(Rep1(1, 100))) {
if (f[i]) {
for (int j : g[i]) {
f[j] = true;
}
}
}
for (int i : Rep1(0, 100)) {
if (!f[i]) {
need[i] = false;
}
}
}
vector<int> U;
for (int i : Rep1(0, 100)) {
if (need[i]) {
U.push_back(i);
}
}
OUT(Sz(U));
vector<vector<pair<int, int>>> g(Sz(U));
for (auto [i, j, x] : edges) {
if (!need[i] || !need[j]) {
continue;
}
i = int(ranges::lower_bound(U, i) - U.begin());
j = int(ranges::lower_bound(U, j) - U.begin());
g[i].emplace_back(j + 1, x);
}
for (int i : Rep(0, Sz(g))) {
OUT(Sz(g[i]), g[i]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Solve();
}
#elif __INCLUDE_LEVEL__ == 1
#include <bits/stdc++.h>
template <class T> concept Range = std::ranges::range<T> && !std::convertible_to<T, std::string_view>;
template <class T> concept Tuple = std::__is_tuple_like<T>::value && !Range<T>;
namespace std {
istream& operator>>(istream& is, Range auto&& r) {
for (auto&& e : r) is >> e;
return is;
}
istream& operator>>(istream& is, Tuple auto&& t) {
apply([&](auto&... xs) { (is >> ... >> xs); }, t);
return is;
}
ostream& operator<<(ostream& os, Range auto&& r) {
auto sep = "";
for (auto&& e : r) os << exchange(sep, " ") << e;
return os;
}
ostream& operator<<(ostream& os, Tuple auto&& t) {
auto sep = "";
apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t);
return os;
}
} // namespace std
using namespace std;
#define Rev views::reverse
#define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__)
#define Rep1(...) [](int l, int r) { return Rep(l, r + 1); }(__VA_ARGS__)
#define Sz(r) int(size(r))
#define IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')
#endif // __INCLUDE_LEVEL__ == 1
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
input:
5 7
output:
5 1 2 1 2 3 0 4 1 1 5 1 2 5 1 5 0 0
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
10 27
output:
16 2 2 1 7 1 2 3 0 4 1 1 5 1 2 6 1 15 0 2 16 0 16 1 2 16 1 16 0 2 8 0 9 1 2 10 0 14 1 1 11 0 2 12 0 15 1 2 13 1 15 0 2 16 0 16 1 2 16 1 16 0 2 15 0 15 1 2 16 0 16 1 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 13
output:
11 2 2 1 5 1 2 3 0 4 1 1 11 1 2 11 1 11 0 2 6 0 7 1 2 8 0 10 1 1 9 0 2 11 0 11 1 2 11 1 11 0 2 11 0 11 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 1000000
output:
57 20 57 1 56 1 55 1 54 1 53 1 52 1 51 1 50 1 49 1 48 1 47 1 46 1 45 1 44 1 43 1 42 1 41 1 40 1 39 1 2 1 2 3 0 4 1 2 5 0 40 1 2 6 1 40 0 2 7 0 41 1 2 8 1 41 0 2 9 0 42 1 1 10 0 2 11 0 43 1 2 12 1 43 0 2 13 0 44 1 1 14 0 2 15 0 45 1 1 16 0 2 17 0 46 1 1 18 0 2 19 0 47 1 1 20 0 2 21 0 48 1 2 22 1 48 0...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
7 9
output:
7 2 2 1 4 1 1 3 1 1 7 1 1 5 0 1 6 0 2 7 0 7 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
3 7
output:
5 2 2 1 3 1 1 5 1 2 4 0 4 1 2 5 0 5 1 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 5
output:
5 3 5 1 4 1 2 1 1 3 0 2 5 0 5 1 2 5 0 5 1 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1 4
output:
5 3 5 1 4 1 2 1 1 3 0 1 5 0 2 5 0 5 1 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
8 9
output:
5 1 2 1 1 3 0 1 4 0 2 5 0 5 1 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
7 51
output:
17 4 2 1 14 1 13 1 4 1 1 3 1 1 17 1 2 5 0 6 1 2 7 0 14 1 1 8 0 2 9 0 15 1 1 10 0 2 11 0 16 1 2 12 1 16 0 2 17 0 17 1 2 17 1 17 0 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
51 79
output:
21 2 2 1 10 1 1 3 1 2 4 0 5 1 2 6 0 19 1 2 7 1 19 0 1 8 1 2 9 1 20 0 1 21 1 2 21 1 21 0 1 11 0 1 12 0 2 13 0 14 1 2 15 0 19 1 2 16 1 19 0 2 17 0 20 1 2 18 1 20 0 2 21 0 21 1 2 21 1 21 0 2 20 0 20 1 2 21 0 21 1 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
92 99
output:
14 1 2 1 2 3 0 4 1 1 5 1 1 6 0 1 7 1 1 8 0 1 9 1 1 10 0 2 11 0 13 1 2 12 1 13 0 2 14 0 14 1 2 14 1 14 0 2 14 0 14 1 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
27 36
output:
16 2 2 1 8 1 1 3 1 2 4 0 5 1 1 6 1 2 7 1 15 0 1 16 1 2 16 1 16 0 1 9 0 1 10 0 2 11 0 12 1 2 13 0 15 1 1 14 0 2 16 0 16 1 1 16 0 2 16 0 16 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
55 84
output:
23 2 2 1 10 1 1 3 1 2 4 0 5 1 1 6 1 2 7 1 21 0 1 8 1 2 9 1 22 0 1 23 1 2 23 1 23 0 1 11 0 2 12 0 13 1 2 14 0 20 1 1 15 0 2 16 0 21 1 2 17 1 21 0 2 18 0 22 1 1 19 0 2 23 0 23 1 1 23 0 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
297208 929600
output:
91 2 2 1 37 1 2 3 0 4 1 2 5 0 75 1 2 6 1 75 0 1 7 1 2 8 1 76 0 2 9 0 77 1 2 10 1 77 0 2 11 0 78 1 2 12 1 78 0 2 13 0 79 1 2 14 1 79 0 1 15 1 2 16 1 80 0 2 17 0 81 1 2 18 1 81 0 2 19 0 82 1 2 20 1 82 0 2 21 0 83 1 2 22 1 83 0 1 23 1 2 24 1 84 0 1 25 1 2 26 1 85 0 1 27 1 2 28 1 86 0 1 29 1 2 30 1 87 0...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
45728 589156
output:
83 5 2 1 67 1 66 1 65 1 31 1 2 3 0 4 1 1 5 1 2 6 1 70 0 1 7 1 2 8 1 71 0 2 9 0 72 1 2 10 1 72 0 2 11 0 73 1 2 12 1 73 0 1 13 1 2 14 1 74 0 2 15 0 75 1 2 16 1 75 0 1 17 1 2 18 1 76 0 2 19 0 77 1 2 20 1 77 0 1 21 1 2 22 1 78 0 2 23 0 79 1 2 24 1 79 0 2 25 0 80 1 2 26 1 80 0 2 27 0 81 1 2 28 1 81 0 2 2...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
129152 138000
output:
68 2 2 1 28 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 2 8 0 9 1 2 10 0 59 1 2 11 1 59 0 2 12 0 60 1 2 13 1 60 0 1 14 1 2 15 1 61 0 2 16 0 62 1 2 17 1 62 0 2 18 0 63 1 2 19 1 63 0 2 20 0 64 1 2 21 1 64 0 2 22 0 65 1 2 23 1 65 0 2 24 0 66 1 2 25 1 66 0 2 26 0 67 1 2 27 1 67 0 2 68 0 68 1 2 68 1 68 0 1 29 0 1 30...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
245280 654141
output:
86 3 2 1 68 1 33 1 1 3 1 1 4 1 2 5 0 6 1 1 7 1 2 8 1 73 0 1 9 1 2 10 1 74 0 1 11 1 2 12 1 75 0 1 13 1 2 14 1 76 0 1 15 1 2 16 1 77 0 2 17 0 78 1 2 18 1 78 0 2 19 0 79 1 2 20 1 79 0 2 21 0 80 1 2 22 1 80 0 1 23 1 2 24 1 81 0 2 25 0 82 1 2 26 1 82 0 2 27 0 83 1 2 28 1 83 0 2 29 0 84 1 2 30 1 84 0 2 31...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
202985 296000
output:
81 2 2 1 34 1 1 3 1 2 4 0 5 1 2 6 0 67 1 2 7 1 67 0 2 8 0 68 1 2 9 1 68 0 1 10 1 2 11 1 69 0 1 12 1 2 13 1 70 0 2 14 0 71 1 2 15 1 71 0 2 16 0 72 1 2 17 1 72 0 2 18 0 73 1 2 19 1 73 0 1 20 1 2 21 1 74 0 1 22 1 2 23 1 75 0 1 24 1 2 25 1 76 0 2 26 0 77 1 2 27 1 77 0 1 28 1 2 29 1 78 0 2 30 0 79 1 2 31...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
438671 951305
output:
90 2 2 1 36 1 1 3 1 2 4 0 5 1 1 6 1 2 7 1 75 0 2 8 0 76 1 2 9 1 76 0 1 10 1 2 11 1 77 0 1 12 1 2 13 1 78 0 2 14 0 79 1 2 15 1 79 0 2 16 0 80 1 2 17 1 80 0 2 18 0 81 1 2 19 1 81 0 1 20 1 2 21 1 82 0 1 22 1 2 23 1 83 0 2 24 0 84 1 2 25 1 84 0 2 26 0 85 1 2 27 1 85 0 2 28 0 86 1 2 29 1 86 0 1 30 1 2 31...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
425249 739633
output:
88 2 2 1 36 1 1 3 1 2 4 0 5 1 2 6 0 73 1 2 7 1 73 0 1 8 1 2 9 1 74 0 1 10 1 2 11 1 75 0 1 12 1 2 13 1 76 0 1 14 1 2 15 1 77 0 1 16 1 2 17 1 78 0 2 18 0 79 1 2 19 1 79 0 1 20 1 2 21 1 80 0 2 22 0 81 1 2 23 1 81 0 2 24 0 82 1 2 25 1 82 0 1 26 1 2 27 1 83 0 2 28 0 84 1 2 29 1 84 0 2 30 0 85 1 2 31 1 85...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
551207 961718
output:
56 1 2 1 2 3 0 4 1 2 5 0 39 1 2 6 1 39 0 2 7 0 40 1 1 8 0 2 9 0 41 1 2 10 1 41 0 1 11 1 1 12 0 1 13 1 2 14 1 43 0 2 15 0 44 1 1 16 0 1 17 1 2 18 1 45 0 2 19 0 46 1 2 20 1 46 0 2 21 0 47 1 1 22 0 1 23 1 1 24 0 2 25 0 49 1 2 26 1 49 0 2 27 0 50 1 1 28 0 1 29 1 2 30 1 51 0 2 31 0 52 1 2 32 1 52 0 2 33 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
114691 598186
output:
84 4 2 1 67 1 66 1 31 1 1 3 1 1 4 1 2 5 0 6 1 2 7 0 72 1 2 8 1 72 0 2 9 0 73 1 2 10 1 73 0 2 11 0 74 1 2 12 1 74 0 2 13 0 75 1 2 14 1 75 0 2 15 0 76 1 2 16 1 76 0 2 17 0 77 1 2 18 1 77 0 2 19 0 78 1 2 20 1 78 0 2 21 0 79 1 2 22 1 79 0 2 23 0 80 1 2 24 1 80 0 2 25 0 81 1 2 26 1 81 0 2 27 0 82 1 2 28 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
234654 253129
output:
46 1 2 1 1 3 1 1 4 1 2 5 0 6 1 2 7 0 33 1 1 8 0 1 9 1 2 10 1 34 0 2 11 0 35 1 2 12 1 35 0 1 13 1 2 14 1 36 0 2 15 0 37 1 1 16 0 2 17 0 38 1 1 18 0 1 19 1 2 20 1 39 0 2 21 0 40 1 2 22 1 40 0 2 23 0 41 1 1 24 0 1 25 1 1 26 0 1 27 1 2 28 1 43 0 1 29 1 1 30 0 1 31 1 1 32 0 2 46 0 46 1 2 46 1 46 0 2 34 0...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
554090 608599
output:
52 1 2 1 1 3 0 1 4 0 2 5 0 6 1 2 7 0 37 1 1 8 0 1 9 1 2 10 1 38 0 1 11 1 1 12 0 1 13 1 1 14 0 2 15 0 41 1 2 16 1 41 0 1 17 1 1 18 0 2 19 0 43 1 1 20 0 2 21 0 44 1 2 22 1 44 0 2 23 0 45 1 1 24 0 1 25 1 2 26 1 46 0 1 27 1 1 28 0 2 29 0 48 1 2 30 1 48 0 1 31 1 1 32 0 2 33 0 50 1 2 34 1 50 0 1 35 1 2 36...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed