QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#707262 | #9519. Build a Computer | becaido | AC ✓ | 0ms | 3744kb | C++20 | 2.6kb | 2024-11-03 15:19:24 | 2024-11-03 15:19:25 |
Judging History
answer
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << "\n";}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int M = 1e6 + 5;
const int N = 1005;
int L, R, sz, tz;
bool is[M];
int mx, to[N][2], a[N];
vector<pair<int, int>> v, adj[N];
void solve() {
cin >> L >> R;
for (int i = L; i <= R;) {
int len = 1;
while (i % (len * 2) == 0) len *= 2;
while (i + len - 1 > R) len /= 2;
int j = i + len - 1;
v.pb(i, j);
i = j + 1;
}
sz = tz = 1;
for (auto [l, r] : v) {
int n = __lg(l) + 1, len = __lg(r - l + 1);
mx = max(mx, len);
for (int pos = 1, i = 1, p = n - 1; i <= n - len; i++, p--) {
int b = l >> p & 1;
if (to[pos][b] == 0) to[pos][b] = ++tz;
pos = to[pos][b];
}
}
sz++;
FOR (i, 1, mx) {
sz++;
adj[sz - 1].pb(sz, 0);
adj[sz - 1].pb(sz, 1);
}
a[1] = 1;
for (auto [l, r] : v) {
int n = __lg(l) + 1, len = __lg(r - l + 1);
mx = max(mx, len);
for (int pos = 1, i = 1, p = n - 1; i <= n - len; i++, p--) {
int b = l >> p & 1, nxt = to[pos][b];
if (i < n - len) {
if (a[nxt] == 0) a[nxt] = ++sz;
pos = nxt;
continue;
}
int j = mx + 2 - len;
adj[a[pos]].pb(j, b);
}
}
auto dfs = [&](auto dfs, int pos)->void {
int nxt = to[pos][0];
if (nxt) {
if (a[nxt]) adj[a[pos]].pb(a[nxt], 0);
dfs(dfs, nxt);
}
nxt = to[pos][1];
if (nxt) {
if (a[nxt]) adj[a[pos]].pb(a[nxt], 1);
dfs(dfs, nxt);
}
};
dfs(dfs, 1);
int x = mx + 2;
swap(adj[x], adj[sz]);
FOR (i, 1, sz) for (auto &[j, y] : adj[i]) {
if (j == x) j = sz;
else if (j == sz) j = x;
}
cout << sz << '\n';
FOR (i, 1, sz) {
cout << adj[i].size();
for (auto [j, x] : adj[i]) cout << ' ' << j << ' ' << x;
cout << '\n';
}
}
int main() {
Waimai;
solve();
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3736kb
input:
5 7
output:
5 1 4 1 2 5 0 5 1 1 5 1 2 2 1 3 0 0
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 27
output:
8 1 6 1 2 3 0 3 1 2 4 0 4 1 2 8 0 8 1 1 3 0 4 3 1 2 0 7 0 5 1 1 4 1 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
5 13
output:
7 1 5 1 2 3 0 3 1 2 7 0 7 1 1 3 0 4 3 1 2 0 6 0 4 1 1 7 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
1 1000000
output:
39 20 39 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 2 1 21 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 19 0 19 1 2 39 0 39 1 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
7 9
output:
6 1 4 1 2 6 0 6 1 1 2 0 2 3 0 5 1 1 6 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
3 7
output:
5 2 2 1 4 1 2 3 0 3 1 2 5 0 5 1 1 5 1 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 5
output:
4 3 4 1 2 1 3 1 2 4 0 4 1 1 2 0 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
1 4
output:
5 3 5 1 2 1 4 1 2 5 0 5 1 1 5 0 1 3 0 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
8 9
output:
5 1 4 1 2 5 0 5 1 1 2 0 1 3 0 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
7 51
output:
9 3 3 1 2 1 7 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 9 0 9 1 1 4 0 2 2 0 8 1 2 9 1 6 0 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
51 79
output:
12 1 7 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 12 0 12 1 1 2 0 2 6 0 8 1 2 3 1 9 0 2 4 1 10 0 1 11 1 1 12 1 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
92 99
output:
11 1 5 1 2 3 0 3 1 2 11 0 11 1 1 2 0 2 6 0 9 1 1 7 1 1 8 1 1 2 1 1 10 0 1 4 0 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
27 36
output:
12 1 5 1 2 3 0 3 1 2 12 0 12 1 1 12 0 2 9 0 6 1 2 2 1 7 0 1 8 1 1 12 1 1 10 0 2 2 0 11 1 1 4 0 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
55 84
output:
16 1 7 1 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 16 0 16 1 1 16 0 2 12 0 8 1 2 3 1 9 0 1 10 1 1 11 1 1 16 1 2 2 0 13 1 1 14 0 2 4 0 15 1 1 6 0 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
297208 929600
output:
53 1 21 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 19 0 19 1 2 53 0 53 1 1 53 0 4 3 1 2 0 22 0 36 1 2 4 1 23 0 1 24 1 2 6 1 25 0 2 7 1 26 0 2 8 1 27 0 1 28 1 2 1...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
45728 589156
output:
47 4 4 1 3 1 2 1 21 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 19 0 19 1 2 47 0 47 1 1 47 0 2 6 1 22 0 2 31 0 23 1 1 24 1 2 9 1 25 0 2 10 1 26 0 1 27 1 2 12 1 28...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
129152 138000
output:
39 1 15 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 39 0 39 1 1 39 0 2 24 0 16 1 1 17 1 1 18 1 1 19 1 1 20 1 2 4 1 21 0 2 5 1 22 0 2 6 1 23 0 1 7 1 1 25 0 1 26 0 1 27 0 2 2 0 28 1 2 3 0 29 1 1 30 0 2 5 0 31 1 2 6 0 32 1 1 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
245280 654141
output:
49 2 2 1 21 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 19 0 19 1 2 49 0 49 1 1 19 0 2 33 0 22 1 1 23 1 2 6 1 24 0 1 25 1 1 26 1 1 27 1 1 28 1 1 29 1 2 12 1 30 0 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
202985 296000
output:
51 1 18 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 51 0 51 1 1 51 0 2 35 0 19 1 2 2 1 20 0 2 3 1 21 0 2 4 1 22 0 1 23 1 1 24 1 2 7 1 25 0 2 8 1 26 0 2 9 1 27 0 1 28 1 1 29 1 1 30 1 2 13...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
438671 951305
output:
54 1 21 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 19 0 19 1 2 54 0 54 1 1 19 0 2 2 0 22 1 4 4 1 3 0 23 0 39 1 1 24 1 2 6 1 25 0 1 26 1 1 27 1 2 9 1 28 0 2 10 1 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
425249 739633
output:
54 1 20 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 54 0 54 1 1 18 0 2 38 0 21 1 2 3 1 22 0 2 4 1 23 0 1 24 1 1 25 1 1 26 1 1 27 1 1 28 1 2 10 1 29 0 1 30 1 2 12 ...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
551207 961718
output:
56 1 20 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 56 0 56 1 1 56 0 2 21 0 39 1 2 2 1 22 0 2 3 1 23 0 2 4 1 24 0 1 25 1 1 26 1 2 7 1 27 0 1 28 1 2 9 1 29 0 2 10 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
114691 598186
output:
54 3 3 1 2 1 21 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 19 0 19 1 2 54 0 54 1 1 54 0 2 37 0 22 1 1 23 1 2 7 1 24 0 2 8 1 25 0 2 9 1 26 0 2 10 1 27 0 2 11 1 28...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
234654 253129
output:
44 1 16 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 44 0 44 1 1 14 0 1 17 1 1 18 1 2 19 0 32 1 2 2 1 20 0 1 21 1 2 4 1 22 0 1 23 1 2 6 1 24 0 2 7 1 25 0 1 26 1 2 9 1 27 0 2 10 1 28 0 1 29 1 1 30 1 1 31 1 1 14 1...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
554090 608599
output:
48 1 18 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 48 0 48 1 1 14 0 1 19 0 1 20 0 2 21 0 36 1 2 2 1 22 0 1 23 1 1 24 1 1 25 1 2 6 1 26 0 1 27 1 2 8 1 28 0 2 9 1 29 0 2 10 1 30 0 1 31 1 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed