QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#692237 | #9519. Build a Computer | OldMemory | AC ✓ | 1ms | 3824kb | C++14 | 7.4kb | 2024-10-31 14:09:38 | 2024-10-31 14:09:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;
bool multi = 0;
vector<vector<PII>> adj1(10000);
vector<vector<PII>> adj2(10000);
void add(int a, int b, int c) {
// cerr << "ADDEDGES:" << a << ' ' << b << ' ' << c << '\n';
adj1[a].push_back({b, c});
adj2[b].push_back({a, c});
}
int L, R, lhi, rhi;
int S = 21, T = 0, idx = 21;
void solveVal(int start, int num) {
int hiw = -1;
for(int i = 20; i >= 0; i--) {
if(num >> i & 1) {
hiw = i;
break;
}
}
// if(hiw == -1) {
// return;
// }
for(int i = hiw; i >= 0; i--) {
int from = -1, to = -1;
if(i == hiw) {
from = start;
}else{
from = idx;
}
if(i == 0) {
to = T;
}else{
to = ++idx;
}
add(from, to, num >> i & 1);
// cerr << from << ' ' << to << '\n';
}
}
void solveUSame1(int startl, int startr, int l, int r) {
// cerr << "START:" << start << '\n';
int lhi = 0, rhi = 0;
for(int i = 20; i >= 0; i--) {
if(l >> i & 1) {
lhi = max(lhi, i);
}
if(r >> i & 1) {
rhi = max(rhi, i);
}
}
add(startr, ++idx, 1);
// cerr << start << ' ' << idx << '\n';
for(int i = rhi - 1; i > lhi; i--) {
add(idx, i - 1, 0);
add(idx, i - 1, 1);
}
// cerr << "JIDWJAIODJWOAJD: " << startl << ' ' << startr << '\n';
// solveVal(startl, l);
// solveVal(startr, r);
if(l != 0) {
int la = startl;
for(int i = lhi; i >= 0; i--) {
if(l >> i & 1) {
add(la, ++idx, 1);
la = idx;
}else{
add(la, i, 1);
add(la, ++idx, 0);
la = idx;
}
}
}
int la = startr;
add(la, ++idx, 1);
// cerr << "DWAJ:" << la << ' ' << idx << ' ' << 1 << '\n';
la = idx;
// cerr << l << ' ' << r << '\n';
for(int i = rhi - 1; i >= 0; i--) {
if(r >> i & 1) {
// cerr << "DWAJ:" << la << ' ' << i << ' ' << 0 << '\n';
add(la, i, 0);
add(la, ++idx, 1);
la = idx;
}else{
add(la, ++idx, 0);
la = idx;
}
}
}
void solveUSame2(int startl, int startr, int l, int r) {
// cerr << "START:" << start << '\n';
int lhi = 0, rhi = 0;
for(int i = 20; i >= 0; i--) {
if(l >> i & 1) {
lhi = max(lhi, i);
}
if(r >> i & 1) {
rhi = max(rhi, i);
}
}
add(startr, ++idx, 0);
int la = idx;
// cerr << start << ' ' << idx << '\n';
for(int i = rhi - 1; i > lhi; i--) {
add(la, i, 1);
add(la, ++idx, 0);
la = idx;
}
// cerr << "JIDWJAIODJWOAJD: " << startl << ' ' << startr << '\n';
// solveVal(startl, l);
// solveVal(startr, r);
if(l != 0) {
int la = startl;
for(int i = lhi; i >= 0; i--) {
if(l >> i & 1) {
add(la, ++idx, 1);
la = idx;
}else{
add(la, i, 1);
add(la, ++idx, 0);
la = idx;
}
}
}
la = startr;
add(la, ++idx, 1);
// cerr << "DWAJ:" << la << ' ' << idx << ' ' << 1 << '\n';
la = idx;
// cerr << l << ' ' << r << '\n';
for(int i = rhi - 1; i >= 0; i--) {
if(r >> i & 1) {
// cerr << "DWAJ:" << la << ' ' << i << ' ' << 0 << '\n';
add(la, i, 0);
add(la, ++idx, 1);
la = idx;
}else{
add(la, ++idx, 0);
la = idx;
}
}
}
void solve() {
cin >> L >> R;
// for(int i = 20; i >= 0; i--) {
// cout << (R >> i & 1);
// }
// cout << '\n';
// for(int i = 20; i >= 0; i--) {
// cout << (L >> i & 1);
// }
// cout << '\n';
for(int i = 20; i >= 1; i--) {
add(i, i - 1, 0);
add(i, i - 1, 1);
}
for(int i = 20; i >= 0; i--) {
if(L >> i & 1) {
lhi = i;
break;
}
}
for(int i = 20; i >= 0; i--) {
if(R >> i & 1) {
rhi = i;
break;
}
}
if(L == R) {
solveVal(S, L);
}else{
int tl = L, tr = R;
if(lhi == rhi) {
for(int i = lhi; i >= 0; i--) {
if(!(L >> i & 1) && (R >> i & 1)) {
int riidx = idx;
for(int j = i; j >= 0; j--) {
if(!(L >> j & 1)) {
add(idx, idx + 1, 0);
idx++;
}else break;
}
int leidx = idx;
solveUSame2(leidx, riidx, L, R);
break;
}else{
// cerr << idx << ' ' << idx + 1 << '\n';
add(idx, idx + 1, L >> i & 1);
++idx;
L = min(L, L ^ (1LL << i));
R = min(R, R ^ (1LL << i));
}
}
idx++;
solveVal(S, tl), solveVal(S, tr);
}else{
solveUSame1(S, S, L, R);
solveVal(S, L), solveVal(S, R);
}
}
vector<int> dist1(idx + 1, INF), dist2(idx + 1, INF), vis(idx + 1);
auto bfs = [&](int start, vector<vector<PII>>& adj, vector<int>& dist) -> void {
queue<int> q;
dist[start] = 0;
q.push(start);
while(q.size()) {
int u = q.front(); q.pop();
for(auto [v, w]: adj[u]) {
if(dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
};
bfs(S, adj1, dist1);
bfs(T, adj2, dist2);
vector<int> nums;
for(int i = 0; i <= idx; i++) {
if(dist1[i] != INF && dist2[i] != INF) {
vis[i] = 1;
nums.push_back(i);
// cout << "JIDJWA: " << i << '\n';
}
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
auto find = [&](int x) -> int {
return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1;
};
// cout << idx << '\n';
// if(idx > 10000) {
// while(1) {}
// }
int tot = nums.size();
vector<vector<PII>> ans(tot + 1);
for(int i = 0; i <= idx; i++) {
if(!vis[i]) continue;
for(auto [v, w]: adj1[i]) {
if(!vis[v]) continue;
ans[find(i)].push_back({find(v), w});
}
}
// for(int i = 1; i <= tot; i++) {
// for(auto [v, w]: ans[i]) {
// cerr << i << ' ' << v << ' ' << w << '\n';
// }
// }
cout << tot << '\n';
for(int i = 1; i <= tot; i++) {
cout << ans[i].size();
for(auto [v, w] : ans[i]) {
cout << ' ' << v << ' ' << w;
}
cout << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
input:
5 7
output:
8 0 3 3 1 5 1 7 1 1 4 1 1 1 0 1 6 0 1 1 1 1 8 1 1 1 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
10 27
output:
19 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 4 6 1 9 1 13 1 16 1 2 3 1 7 0 1 8 1 1 1 1 2 4 0 10 1 1 11 0 2 2 0 12 1 1 1 0 1 14 0 1 15 1 1 1 0 1 17 1 1 18 0 1 19 1 1 1 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
5 13
output:
13 0 2 1 0 1 1 2 2 0 2 1 4 5 1 6 1 9 1 11 1 1 2 1 2 3 0 7 1 1 8 0 1 1 0 1 10 0 1 1 1 1 12 1 1 13 0 1 1 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
1 1000000
output:
53 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 22 1 1 1 35 1 36 18 0 18 1 17 0 17 1 16 0 16 1 15 0 15 1 14 0 14 1 13 0 13 1 12 0 12 1 11 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
1 1
output:
2 0 1 1 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
7 9
output:
10 0 3 3 1 6 1 8 1 1 4 0 1 5 0 1 1 0 1 7 1 1 1 1 1 9 0 1 10 0 1 1 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
3 7
output:
8 0 2 1 0 1 1 3 4 1 6 1 7 1 2 2 0 5 1 1 1 0 1 1 1 1 8 1 1 1 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
1 5
output:
7 0 4 3 1 4 1 1 1 6 1 2 1 0 1 1 1 5 0 1 1 0 1 7 0 1 1 1
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
1 4
output:
5 0 3 3 1 1 1 4 1 2 1 0 1 1 1 5 0 1 1 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
8 9
output:
8 0 2 3 1 6 1 1 4 0 1 5 0 1 1 0 1 7 0 1 8 0 1 1 1
result:
ok ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
7 51
output:
19 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 4 7 1 8 1 13 1 15 1 4 4 0 4 1 3 0 3 1 2 5 0 9 1 1 10 0 1 11 0 2 2 0 12 1 1 1 0 1 14 1 1 1 1 1 16 1 1 17 0 1 18 0 1 19 1 1 1 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
51 79
output:
25 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 4 6 1 9 1 15 1 20 1 1 7 1 2 4 1 8 0 1 3 1 1 10 0 1 11 0 2 4 0 12 1 2 3 0 13 1 2 2 0 14 1 1 1 0 1 16 1 1 17 0 1 18 0 1 19 1 1 1 1 1 21 0 1 22 0 1 23 1 1 24 1 1 25 1 1 1 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
92 99
output:
26 0 2 1 0 1 1 3 4 1 15 1 21 1 2 5 0 10 1 1 6 1 1 7 1 1 8 1 2 2 1 9 0 1 1 1 1 11 0 1 12 0 1 13 0 2 2 0 14 1 1 1 0 1 16 0 1 17 1 1 18 1 1 19 1 1 20 0 1 1 0 1 22 1 1 23 0 1 24 0 1 25 0 1 26 1 1 1 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
27 36
output:
18 0 2 1 0 1 1 2 2 0 2 1 4 5 1 7 1 10 1 14 1 1 6 1 1 3 1 1 8 0 1 9 0 1 3 0 1 11 1 1 12 0 1 13 1 1 1 1 1 15 0 1 16 0 1 17 1 1 18 0 1 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
55 84
output:
23 0 2 1 0 1 1 2 2 0 2 1 2 3 0 3 1 2 4 0 4 1 4 7 1 9 1 13 1 18 1 1 8 1 1 4 1 1 10 0 2 5 0 11 1 1 12 0 1 3 0 1 14 1 1 15 0 1 16 1 1 17 1 1 1 1 1 19 0 1 20 1 1 21 0 1 22 1 1 23 0 1 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
297208 929600
output:
88 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 39 1 52 1 70 1 2 18 1 22 0 2 17 1 23 0 1 24 1 2 15 1 25 0 2 14 1 26 0 2 13 1 27 0 1 28 1 2...
result:
ok ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
45728 589156
output:
86 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 5 20 1 21 1 36 1 53 1 68 1 6 18 0 18 1 17 0 17 1 16 0 16 1 2 15 1 22 0 1 23 1 1 24 1 2 12 1 25 0 2 11 1 26 0 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
129152 138000
output:
76 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 4 15 1 31 1 44 1 60 1 1 16 1 1 17 1 1 18 1 1 19 1 1 20 1 2 11 1 21 0 2 10 1 22 0 2 9 1 23 0 1 24 1 2 7 1 25 0 2 6 1 26 0 2 5 1 27 0 2 4 1 28 0 2 3 1 29 0 2 2 1 30 0 1 1 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
245280 654141
output:
92 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 5 20 1 21 1 38 1 57 1 74 1 2 18 0 18 1 1 22 1 1 23 1 2 15 1 24 0 1 25 1 1 26 1 1 27 1 1 28 1 1 29 1 2 9 1 30 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
202985 296000
output:
80 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 4 18 1 34 1 46 1 63 1 1 19 1 2 16 1 20 0 2 15 1 21 0 2 14 1 22 0 1 23 1 1 24 1 2 11 1 25 0 2 10 1 26 0 2 9 1 27 0 1 28 1 1 29 1 1 30 ...
result:
ok ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
438671 951305
output:
90 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 35 1 54 1 72 1 1 22 1 2 17 1 23 0 1 24 1 2 15 1 25 0 1 26 1 1 27 1 2 12 1 28 0 2 11 1 29 0...
result:
ok ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
425249 739633
output:
92 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 4 20 1 37 1 56 1 74 1 1 21 1 2 17 1 22 0 2 16 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 ...
result:
ok ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
551207 961718
output:
93 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 3 20 1 56 1 75 1 3 21 0 25 0 39 1 1 22 0 1 23 0 1 24 0 1 28 1 2 18 1 26 0 2 17 1 27 0 1 16 1 1 29 1 2 13 1 30...
result:
ok ok
Test #24:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
114691 598186
output:
87 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 5 20 1 21 1 35 1 53 1 69 1 4 18 0 18 1 17 0 17 1 1 22 1 1 23 1 2 14 1 24 0 2 13 1 25 0 2 12 1 26 0 2 11 1 27 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
234654 253129
output:
81 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 3 16 1 48 1 65 1 1 17 1 1 18 1 3 19 0 21 0 34 1 1 20 0 1 22 1 1 14 1 2 12 1 23 0 1 24 1 2 10 1 25 0 2 9 1 26 0 1 27 1 2 7 1 28 0 2 6 1 29 0 1 30 1 1 31 1 1 3...
result:
ok ok
Test #26:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
554090 608599
output:
91 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 3 18 1 54 1 73 1 1 19 0 1 20 0 3 21 0 23 0 38 1 1 22 0 1 24 1 1 16 1 1 25 1 1 26 1 2 12 1 27 0 1 28 1 2 10 1 29 0 2 9 1 30 0 2 8 1 31...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed