QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#693543 | #9519. Build a Computer | ucup-team3519# | AC ✓ | 1ms | 3868kb | C++17 | 1.4kb | 2024-10-31 16:20:59 | 2024-10-31 16:21:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
#define fi first
#define se second
#define V vector
#define pb push_back
typedef long long LL;
void solve() {
int l, r; cin >> l >> r;
int tot = 2;
V<V<pi>> e(101);
map<array<int, 4>, int> mp;
auto dfs = [&](int l, int r, int now, bool prez, auto dfs) -> int {
if(now == -1) return 2;
if(mp.count({l, r, now, prez})) return mp[{l, r, now, prez}];
// int x = ++tot;
int x;
if(prez) x = 1;
else x = ++tot;
if(r >> now & 1) {
int n_r = r - (1 << now);
int n_l = max(0, l - (1 << now));
e[x].pb({dfs(n_l, n_r, now - 1, 0, dfs), 1});
}
if(!(l >> now & 1)) {
int n_l = l;
int n_r = min((1 << now) - 1, r);
if(!prez) e[x].pb({dfs(n_l, n_r, now - 1, prez, dfs), 0});
else dfs(n_l, n_r, now - 1, prez, dfs);
}
return mp[{l, r, now, prez}] = x;
};
dfs(l, r, 19, 1, dfs);
cout << tot << endl;
for(int i = 1; i <= tot; i++) {
int x = i;
cout << e[x].size() << " ";
for(auto [y, w] : e[x]) cout << y << " " << w << " ";
cout << endl;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
// int t; cin >> t;
// while(t--)
solve();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3868kb
input:
5 7
output:
5 1 3 1 0 2 4 1 5 0 2 2 1 2 0 1 2 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
10 27
output:
9 2 3 1 8 1 0 2 4 1 7 0 1 5 0 2 6 1 6 0 2 2 1 2 0 2 5 1 5 0 2 5 1 9 0 1 6 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
5 13
output:
8 2 3 1 7 1 0 2 4 1 6 0 1 5 0 2 2 1 2 0 2 5 1 5 0 2 5 1 8 0 1 2 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 1000000
output:
39 20 3 1 39 1 38 1 36 1 37 1 31 1 32 1 33 1 34 1 35 1 28 1 29 1 30 1 22 1 23 1 24 1 25 1 26 1 27 1 2 1 0 2 4 1 39 0 2 5 1 38 0 2 6 1 36 0 1 7 0 2 8 1 31 0 1 9 0 1 10 0 1 11 0 1 12 0 2 13 1 28 0 1 14 0 1 15 0 2 16 1 22 0 1 17 0 1 18 0 1 19 0 1 20 0 1 21 0 1 2 0 2 23 1 23 0 2 24...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
7 9
output:
7 2 3 1 6 1 0 1 4 0 1 5 0 2 2 1 2 0 1 7 1 1 2 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
3 7
output:
5 2 3 1 5 1 0 2 4 1 4 0 2 2 1 2 0 1 2 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
1 5
output:
4 3 3 1 4 1 2 1 0 1 4 0 2 2 1 2 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
1 4
output:
5 3 3 1 5 1 2 1 0 1 4 0 1 2 0 2 2 1 2 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
8 9
output:
5 1 3 1 0 1 4 0 1 5 0 2 2 1 2 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
7 51
output:
11 4 3 1 8 1 9 1 10 1 0 2 4 1 8 0 1 5 0 1 6 0 2 7 1 7 0 2 2 1 2 0 2 9 1 9 0 2 6 1 6 0 1 11 1 1 2 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
51 79
output:
13 2 3 1 9 1 0 1 4 0 1 5 0 2 6 1 6 0 2 7 1 7 0 2 8 1 8 0 2 2 1 2 0 1 10 1 2 6 1 11 0 2 7 1 12 0 1 13 1 1 2 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
92 99
output:
11 1 3 1 0 2 4 1 9 0 1 5 0 1 6 0 1 7 0 2 8 1 8 0 2 2 1 2 0 1 10 1 1 11 1 1 7 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
27 36
output:
13 2 3 1 10 1 0 1 4 0 1 5 0 2 6 1 8 0 1 7 0 1 2 0 2 9 1 9 0 2 2 1 2 0 1 11 1 2 8 1 12 0 1 13 1 1 2 1
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
55 84
output:
17 2 3 1 13 1 0 1 4 0 2 5 1 11 0 1 6 0 2 7 1 9 0 1 8 0 1 2 0 2 10 1 10 0 2 2 1 2 0 2 12 1 12 0 2 9 1 9 0 1 14 1 2 12 1 15 0 1 16 1 1 17 1 1 2 1
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
297208 929600
output:
54 2 3 1 40 1 0 2 4 1 39 0 2 5 1 35 0 1 6 0 1 7 0 1 8 0 2 9 1 33 0 1 10 0 2 11 1 32 0 2 12 1 31 0 2 13 1 30 0 2 14 1 28 0 1 15 0 2 16 1 22 0 1 17 0 1 18 0 1 19 0 1 20 0 1 21 0 1 2 0 2 23 1 23 0 2 24 1 24 0 2 25 1 25 0 2 26 1 26 0 2 27 1 27 0 2 2 1 2 0 2 29 1 29 0 2 22 1 2...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
45728 589156
output:
49 5 3 1 37 1 38 1 39 1 40 1 0 1 4 0 1 5 0 1 6 0 2 7 1 36 0 2 8 1 35 0 2 9 1 34 0 2 10 1 33 0 2 11 1 32 0 2 12 1 30 0 1 13 0 2 14 1 28 0 1 15 0 2 16 1 27 0 2 17 1 24 0 1 18 0 1 19 0 2 20 1 22 0 1 21 0 1 2 0 2 23 1 23 0 2 2 1 2 0 2 25 1 25 0 2 26 1 26 0 2 22 1 22 0 2 24 1 24...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
129152 138000
output:
40 2 3 1 32 1 0 1 4 0 1 5 0 1 6 0 1 7 0 2 8 1 31 0 2 9 1 29 0 1 10 0 2 11 1 28 0 2 12 1 24 0 1 13 0 1 14 0 1 15 0 2 16 1 20 0 1 17 0 1 18 0 1 19 0 1 2 0 2 21 1 21 0 2 22 1 22 0 2 23 1 23 0 2 2 1 2 0 2 25 1 25 0 2 26 1 26 0 2 27 1 27 0 2 20 1 20 0 2 24 1 24 0 2 30 1 30 0 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
245280 654141
output:
50 3 3 1 37 1 39 1 0 1 4 0 1 5 0 2 6 1 36 0 2 7 1 35 0 2 8 1 34 0 2 9 1 33 0 2 10 1 32 0 2 11 1 30 0 1 12 0 2 13 1 29 0 2 14 1 26 0 1 15 0 1 16 0 2 17 1 25 0 2 18 1 24 0 2 19 1 23 0 2 20 1 22 0 1 21 0 2 2 1 2 0 2 21 1 21 0 2 22 1 22 0 2 23 1 23 0 2 24 1 24 0 2 27 1 27 0 2 2...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
202985 296000
output:
52 2 3 1 36 1 0 1 4 0 1 5 0 2 6 1 31 0 1 7 0 1 8 0 1 9 0 1 10 0 2 11 1 27 0 1 12 0 1 13 0 1 14 0 2 15 1 21 0 1 16 0 1 17 0 1 18 0 1 19 0 1 20 0 1 2 0 2 22 1 22 0 2 23 1 23 0 2 24 1 24 0 2 25 1 25 0 2 26 1 26 0 2 2 1 2 0 2 28 1 28 0 2 29 1 29 0 2 30 1 30 0 2 21 1 21 0 2 ...
result:
ok ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
438671 951305
output:
56 2 3 1 39 1 0 2 4 1 38 0 2 5 1 36 0 1 6 0 2 7 1 31 0 1 8 0 1 9 0 1 10 0 1 11 0 2 12 1 24 0 1 13 0 1 14 0 1 15 0 1 16 0 1 17 0 1 18 0 2 19 1 22 0 1 20 0 1 21 0 2 2 1 2 0 2 23 1 23 0 2 21 1 21 0 2 25 1 25 0 2 26 1 26 0 2 27 1 27 0 2 28 1 28 0 2 29 1 29 0 2 30 1 30 0 2 22...
result:
ok ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
425249 739633
output:
55 2 3 1 38 1 0 1 4 0 2 5 1 37 0 2 6 1 35 0 1 7 0 2 8 1 32 0 1 9 0 1 10 0 2 11 1 29 0 1 12 0 1 13 0 2 14 1 26 0 1 15 0 1 16 0 2 17 1 25 0 2 18 1 22 0 1 19 0 1 20 0 1 21 0 2 2 1 2 0 2 23 1 23 0 2 24 1 24 0 2 21 1 21 0 2 22 1 22 0 2 27 1 27 0 2 28 1 28 0 2 25 1 25 0 2 30 1 ...
result:
ok ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
551207 961718
output:
56 1 3 1 0 2 4 1 39 0 2 5 1 37 0 1 6 0 2 7 1 35 0 1 8 0 2 9 1 33 0 1 10 0 2 11 1 32 0 2 12 1 29 0 1 13 0 1 14 0 2 15 1 27 0 1 16 0 2 17 1 26 0 2 18 1 24 0 1 19 0 2 20 1 23 0 2 21 1 22 0 1 2 0 2 2 1 2 0 2 22 1 22 0 2 25 1 25 0 2 23 1 23 0 2 24 1 24 0 2 28 1 28 0 2 26 1 26 0...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
114691 598186
output:
55 4 3 1 38 1 39 1 40 1 0 1 4 0 1 5 0 2 6 1 35 0 1 7 0 1 8 0 2 9 1 29 0 1 10 0 1 11 0 1 12 0 1 13 0 1 14 0 2 15 1 27 0 1 16 0 2 17 1 25 0 1 18 0 2 19 1 23 0 1 20 0 2 21 1 22 0 1 2 0 2 2 1 2 0 2 24 1 24 0 2 22 1 22 0 2 26 1 26 0 2 23 1 23 0 2 28 1 28 0 2 25 1 25 0 2 30 1 3...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
234654 253129
output:
44 1 3 1 0 1 4 1 1 5 1 2 6 1 31 0 1 7 0 2 8 1 30 0 2 9 1 29 0 2 10 1 26 0 1 11 0 1 12 0 2 13 1 25 0 2 14 1 22 0 1 15 0 1 16 0 2 17 1 20 0 1 18 0 1 19 0 2 2 1 2 0 2 21 1 21 0 2 19 1 19 0 2 23 1 23 0 2 24 1 24 0 2 20 1 20 0 2 22 1 22 0 2 27 1 27 0 2 28 1 28 0 2 25 1 25 0 2 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
554090 608599
output:
48 1 3 1 0 1 4 0 1 5 0 2 6 1 33 0 1 7 0 2 8 1 30 0 1 9 0 1 10 0 2 11 1 27 0 1 12 0 1 13 0 2 14 1 25 0 1 15 0 2 16 1 23 0 1 17 0 2 18 1 22 0 1 19 0 2 20 1 20 0 2 21 1 21 0 2 2 1 2 0 2 19 1 19 0 2 24 1 24 0 2 22 1 22 0 2 26 1 26 0 2 23 1 23 0 2 28 1 28 0 2 29 1 29 0 2 25 1 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed