QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#746520 | #9519. Build a Computer | ucup-team3702# | AC ✓ | 0ms | 3944kb | C++14 | 2.8kb | 2024-11-14 14:53:08 | 2024-11-14 14:53:08 |
Judging History
answer
#include <map>
#include <set>
#include <list>
#include <array>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <memory>
#include <vector>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define per(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << " \n"[_ == r]
const int K = 20;
const int N = 1e2 + 10;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + (c - 48);
return x * f;
}
int L, R, n, rt, in[N], out[N];
bool tag[N];
vector <int> id;
vector <pair <int, int>> e[N];
void add(int u, int v, int o) {
e[u].emplace_back(make_pair(v, o));
}
void work() {
for (int i = 0; i < n; ++i) {
for (auto [j, o] : e[i]) ++in[j], ++out[i];
}
int k = 0;
rep(i, 0, K) if (in[i] > 2 * (i < K)) k = i;
rep(i, 0, k) id.emplace_back(i);
for (int i = K + 1; i < n; ++i) {
if (i == rt || (in[i] && out[i])) {
id.emplace_back(i);
}
}
for (int i : id) tag[i] = true;
}
int rk(int i) {
return lower_bound(id.begin(), id.end(), i) - id.begin() + 1;
}
void print() {
int m = id.size();
// pa(id, 0, m - 1);
printf("%d\n", m);
for (int i = 0; i < n; ++i) if (tag[i]) {
printf("%d ", (int) e[i].size());
for (auto [j, o] : e[i]) {
printf("%d %d ", rk(j), o);
}
printf("\n");
}
}
int dfs(int d, int l, int r) {
if (R < l || r < L) return 0;
int u = n++;
if (l == 0 && r == (1 << K) - 1) rt = u;
// cout << "u, d, l, r = " << u << ' ' << d << ' ' << l << ' ' << r << endl;
int mid = (l + r) >> 1;
if (L <= l && mid <= R) {
add(u, d, 0);
} else {
int v = dfs(d - 1, l, mid);
if (l && v && e[v].size()) add(u, v, 0);
}
if (L <= mid + 1 && r <= R) {
add(l == 0 ? rt : u, d, 1);
} else {
int v = dfs(d - 1, mid + 1, r);
// cout << "u, v = " << u << ' ' << v << endl;
if (v && e[v].size()) add(l == 0 ? rt : u, v, 1);
}
return u;
}
int main() {
L = read(), R = read();
n = K + 1;
for (int i = K; i; --i) {
add(i, i - 1, 0);
add(i, i - 1, 1);
}
dfs(K - 1, 0, (1 << K) - 1);
// pv(rt);
work();
// pv(rk(rt));
print();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
input:
5 7
output:
5 0 2 1 0 1 1 1 4 1 2 5 0 2 1 1 1 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
10 27
output:
9 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 6 1 8 1 2 7 0 3 1 1 2 1 2 4 0 9 1 1 3 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
5 13
output:
8 0 2 1 0 1 1 2 2 0 2 1 2 5 1 7 1 2 6 0 2 1 1 1 1 2 3 0 8 1 1 2 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
1 1000000
output:
39 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 20 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1 1
output:
2 0 1 1 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
7 9
output:
7 0 2 1 0 1 1 2 4 1 6 1 1 5 1 1 1 1 1 7 0 1 2 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
3 7
output:
5 0 2 1 0 1 1 2 2 0 2 1 2 5 1 3 1 1 1 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1 5
output:
4 0 2 1 0 1 1 3 1 1 2 1 4 1 1 2 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
1 4
output:
5 0 2 1 0 1 1 3 1 1 2 1 4 1 1 5 0 1 1 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
8 9
output:
5 0 2 1 0 1 1 1 4 1 1 5 0 1 2 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
7 51
output:
11 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 4 7 1 4 1 5 1 9 1 1 8 1 1 1 1 2 5 0 10 1 1 11 0 1 3 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
51 79
output:
13 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 7 1 12 1 1 8 1 2 9 0 4 1 2 10 0 3 1 1 11 1 1 1 1 1 13 0 1 5 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
92 99
output:
11 0 2 1 0 1 1 2 2 0 2 1 1 5 1 2 6 0 9 1 1 7 1 1 8 1 1 3 1 1 10 0 1 11 0 1 3 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
27 36
output:
13 0 2 1 0 1 1 2 2 0 2 1 2 5 1 9 1 1 6 1 2 7 0 3 1 1 8 1 1 1 1 1 10 0 1 11 0 2 3 0 12 1 1 13 0 1 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
55 84
output:
17 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 7 1 12 1 1 8 1 2 9 0 4 1 1 10 1 1 11 1 1 1 1 1 13 0 2 5 0 14 1 1 15 0 2 3 0 16 1 1 17 0 1 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
297208 929600
output:
54 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 21 1 36 1 2 22 0 18 1 2 23 0 17 1 1 24 1 2 25 0 15 1 2 26 0 14 1 2 27 ...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
45728 589156
output:
49 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 5 21 1 17 1 18 1 19 1 31 1 2 22 0 15 1 1 23 1 1 24 1 2 25 0 12 1 2 26 0 1...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
129152 138000
output:
40 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 15 1 24 1 1 16 1 1 17 1 1 18 1 1 19 1 1 20 1 2 21 0 11 1 2 22 0 10 1 2 23 0 9 1 1 8 1 1 25 0 1 26 0 1 27 0 1 28 0 2 13 0 29 1 2 12 0 30 1 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
245280 654141
output:
50 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 3 21 1 19 1 33 1 1 22 1 1 23 1 2 24 0 15 1 1 25 1 1 26 1 1 27 1 1 28 1 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
202985 296000
output:
52 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 18 1 35 1 1 19 1 2 20 0 16 1 2 21 0 15 1 2 22 0 14 1 1 23 1 1 24 1 2 25 0 11 1 2 26 0 10 1 2 27 0 9 1 1 2...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
438671 951305
output:
56 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 21 1 39 1 1 22 1 2 23 0 17 1 1 24 1 2 25 0 15 1 1 26 1 1 27 1 2 28 0 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
425249 739633
output:
55 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 20 1 38 1 1 21 1 2 22 0 17 1 2 23 0 16 1 1 24 1 1 25 1 1 26 1 1 27 1 1 28 1 2 29...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
551207 961718
output:
56 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 1 20 1 2 21 0 39 1 2 22 0 18 1 2 23 0 17 1 2 24 0 16 1 1 25 1 1 26 1 2 27 0 13 1 1 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
114691 598186
output:
55 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 4 21 1 18 1 19 1 37 1 1 22 1 1 23 1 2 24 0 14 1 2 25 0 13 1 2 26 0 12 1 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
234654 253129
output:
44 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 1 16 1 1 17 1 1 18 1 2 19 0 32 1 2 20 0 14 1 1 21 1 2 22 0 12 1 1 23 1 2 24 0 10 1 2 25 0 9 1 1 26 1 2 27 0 7 1 2 28 0 6 1 1 29 1 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
554090 608599
output:
48 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 1 18 1 1 19 0 1 20 0 2 21 0 36 1 2 22 0 16 1 1 23 1 1 24 1 1 25 1 2 26 0 12 1 1 27 1 2 28 0 10 1 2 29 0 9 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed