QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #723856 | #9519. Build a Computer | 287029 | AC ✓ | 1ms | 3856kb | C++20 | 2.5kb | 2024-11-08 01:30:20 | 2024-11-08 01:30:27 |
Judging History
answer
#include <bits/stdc++.h>
#define bit(x) (1LL << (x))
#define lowbit(x) (x & (-x))
#define SQU(x) ((x) * (x))
#define ls id << 1
#define rs id << 1 | 1
//#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int inv2 = (mod + 1) / 2;
ll qpow(ll x,ll y) {
ll res = 1;
while(y) {
if(y & 1) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
void add(int &x,int y) {
x += y;
if(x >= mod) x -= mod;
}
const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
void solve() {
int L,R;cin >> L >> R;
int cnt = 1;
vector <vector <pair <int,int>>> g(100);
vector <int> vis(21,-1),val;
vis[0] = 0;
auto position = [&] (auto &&self,int dep) -> int{
if(vis[dep] != -1) return vis[dep];
vis[dep] = cnt++;
g[vis[dep]].push_back({self(self,dep - 1),0});
g[vis[dep]].push_back({self(self,dep - 1),1});
return vis[dep];
};
auto dfs = [&] (auto&&self,int l,int r,int dep,bool zero) -> int {
if(dep == -1) return zero ? -1 : position(position,0);
if(l == 0 && r == bit(dep + 1) - 1 && (!zero)) return position(position,dep + 1);
int num = bit(dep),now = cnt;
if((l & num) == (r & num)) {
int u = self(self,l & (num - 1),r & (num - 1),dep - 1,((zero == true) && ((l & num) == 0)));
if(zero) val.push_back(u);
else if(u != -1) {
now = cnt++;
g[now].push_back({u,((l >> dep) & 1)});
}
}else {
int x = self(self,l & (num - 1),num - 1,dep - 1,zero && ((l & num) == 0));
// if(l == 10 && r == 27) cout << x << '\n';
int y = self(self,0,r & (num - 1),dep - 1,false);
if(zero) {
val.push_back(x);
val.push_back(y);
}else {
now = cnt++;
if(x != -1) g[now].push_back({x,0});
if(y != -1) g[now].push_back({y,1});
}
}
return zero ? -1 : now;
};
dfs(dfs,L,R,21,true);
cnt++;
for(auto &x : val) if(x != -1) g[cnt - 1].push_back({x,1});
cout << cnt << '\n';
for(int i = 0;i < cnt;i++) {
cout << g[i].size() << ' ';
for(auto &[x,y] : g[i]) cout << x + 1 << ' ' << y << ' ';
cout << '\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout << fixed << setprecision(20);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
/*
*/
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
input:
5 7
output:
5 0 1 1 1 2 1 0 1 1 2 2 0 3 1 1 4 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
10 27
output:
9 0 2 1 0 1 1 1 2 1 2 2 0 2 1 2 3 0 4 1 2 4 0 4 1 1 4 0 2 6 0 7 1 2 5 1 8 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
5 13
output:
8 0 1 1 1 2 1 0 1 1 2 2 0 3 1 2 3 0 3 1 1 3 0 2 5 0 6 1 2 4 1 7 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
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 1 1 0 1 20 0 1 21 0 1 22 0 1 23 0 1 24 0 2 7 0 25 1 1 26 0 1 27 0 2 1...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
1 1
output:
2 0 1 1 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
7 9
output:
7 0 1 1 1 1 2 1 2 1 0 1 1 1 4 0 1 5 0 2 3 1 6 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 7
output:
5 0 1 1 1 2 4 0 4 1 2 1 0 1 1 2 2 1 3 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 5
output:
4 0 2 1 0 1 1 1 2 0 3 1 1 2 1 3 1
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
1 4
output:
5 0 2 1 0 1 1 1 1 0 1 3 0 3 1 1 2 1 4 1
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
8 9
output:
5 0 2 1 0 1 1 1 2 0 1 3 0 1 4 1
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
7 51
output:
11 0 1 1 1 1 2 1 2 5 0 5 1 2 6 0 6 1 2 1 0 1 1 2 4 0 4 1 1 5 0 1 8 0 2 7 0 9 1 4 3 1 4 1 7 1 10 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
51 79
output:
13 0 1 1 1 1 2 1 2 5 0 5 1 2 1 0 1 1 2 3 0 4 1 2 4 0 4 1 2 6 0 7 1 1 8 1 2 7 0 7 1 1 10 0 1 11 0 2 9 1 12 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
92 99
output:
11 0 2 3 0 3 1 2 1 0 1 1 1 2 1 1 4 1 1 5 1 1 2 0 1 7 0 1 8 0 2 6 0 9 1 1 10 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
27 36
output:
13 0 1 1 1 1 2 1 2 5 0 5 1 2 1 0 1 1 2 3 0 4 1 1 6 1 1 1 0 1 8 0 2 4 0 9 1 1 10 0 1 11 0 2 7 1 12 1
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
55 84
output:
17 0 1 1 1 1 2 1 1 3 1 2 6 0 6 1 2 7 0 7 1 2 1 0 1 1 2 4 0 5 1 1 8 1 2 5 0 5 1 1 1 0 1 11 0 2 6 0 12 1 1 13 0 2 10 0 14 1 1 15 0 2 9 1 16 1
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
297208 929600
output:
54 0 2 3 0 3 1 2 4 0 4 1 2 1 0 1 1 1 2 1 1 5 1 1 6 1 1 7 1 1 8 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 2 0 2 1 2 9 0 10 1 2 10 0 10 1 2 15 0 16 1 2 16 0 16 1 2 17 0 18 1 1 19 1 2 22 0 22 1 2 18 0 18 1 2 20 0 21 1 2 21 0 21 1 2 23 0 24 1 2 24 0 24 1 2 25 0 26 1 ...
result:
ok ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
45728 589156
output:
49 0 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 1 0 1 1 1 2 1 2 2 0 2 1 2 7 0 8 1 1 9 1 2 12 0 12 1 2 8 0 8 1 2 10 0 11 1 1 13 1 2 16 0 16 1 2 11 0 11 1 2 14 0 15 1 2 15 0 15 1 2 17 0 18 1 1 19 1 1 20 1 2 23 0 23 1 2 24 0 24 1 2 18 0 18 1 2 21 0 22 1 2 27 0 27 1 2 22 0 22 1 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
129152 138000
output:
40 0 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 1 0 1 1 1 2 1 2 2 0 2 1 2 9 0 10 1 2 10 0 10 1 2 11 0 12 1 2 12 0 12 1 2 13 0 14 1 1 15 1 1 16 1 1 17 1 1 18 1 1 19 1 2 22 0 22 1 2 14 0 14 1 1 1 0 1 23 0 1 24 0 1 25 0 2 5 0 26 1 1 27 0 1 28 0 1 29 0 2 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
245280 654141
output:
50 0 2 3 0 3 1 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 1 0 1 1 1 2 1 2 2 0 2 1 2 7 0 8 1 2 8 0 8 1 2 9 0 10 1 2 10 0 10 1 2 11 0 12 1 1 13 1 1 14 1 1 15 1 1 16 1 1 17 1 2 20 0 20 1 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2 24 0 24 1 2 12 0 12 1 2 18 0 19 1 1 25 1 1 26 1 2 29 0 29 1 2...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
202985 296000
output:
52 0 1 1 1 2 1 0 1 1 2 2 0 3 1 2 3 0 3 1 2 4 0 5 1 1 6 1 2 9 0 9 1 2 5 0 5 1 2 7 0 8 1 1 10 1 1 11 1 1 12 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 8 0 8 1 2 13 0 14 1 2 14 0 14 1 2 18 0 19 1 2 19 0 19 1 2 20 0 21 1 1 22 1 1 23 1 2 26 0 26 1 2 27 0 27 1 2 21 0 21 1 2 24 0 25...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
438671 951305
output:
56 0 1 1 1 1 2 1 1 3 1 1 4 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 1 0 1 1 2 5 0 6 1 2 6 0 6 1 2 10 0 11 1 2 11 0 11 1 2 12 0 13 1 1 14 1 1 15 1 2 18 0 18 1 2 19 0 19 1 2 13 0 13 1 2 16 0 17 1 2 17 0 17 1 2 20 0 21 1 2 21 0 21 1 2 22 0 23 1 1 24 1 1 25 1 2 28 0 28 1 2 29 0 29 1 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
425249 739633
output:
55 0 1 1 1 2 1 0 1 1 2 2 0 3 1 2 3 0 3 1 2 4 0 5 1 2 5 0 5 1 2 6 0 7 1 2 7 0 7 1 2 8 0 9 1 1 10 1 2 13 0 13 1 2 9 0 9 1 2 11 0 12 1 2 12 0 12 1 2 14 0 15 1 1 16 1 2 19 0 19 1 2 15 0 15 1 2 17 0 18 1 1 20 1 1 21 1 1 22 1 1 23 1 1 24 1 2 27 0 27 1 2 28 0 28 1 2 29 0 29 1 2 ...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
551207 961718
output:
56 0 1 1 1 1 2 1 1 3 1 2 6 0 6 1 2 7 0 7 1 2 1 0 1 1 2 4 0 5 1 2 5 0 5 1 2 8 0 9 1 1 10 1 2 13 0 13 1 2 9 0 9 1 2 11 0 12 1 2 12 0 12 1 2 14 0 15 1 1 16 1 2 19 0 19 1 2 15 0 15 1 2 17 0 18 1 2 18 0 18 1 2 20 0 21 1 1 22 1 2 25 0 25 1 2 21 0 21 1 2 23 0 24 1 1 26 1 1 27 1 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
114691 598186
output:
55 0 1 1 1 1 2 1 2 5 0 5 1 2 1 0 1 1 2 3 0 4 1 2 4 0 4 1 2 6 0 7 1 2 7 0 7 1 2 8 0 9 1 2 9 0 9 1 2 10 0 11 1 2 11 0 11 1 2 12 0 13 1 2 13 0 13 1 2 14 0 15 1 2 15 0 15 1 2 16 0 17 1 2 17 0 17 1 2 18 0 19 1 2 19 0 19 1 2 20 0 21 1 2 21 0 21 1 2 22 0 23 1 2 23 0 23 1 2 24 0 25 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
234654 253129
output:
44 0 2 1 0 1 1 1 2 1 1 3 1 1 4 1 1 5 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 2 0 2 1 2 6 0 7 1 2 7 0 7 1 2 11 0 12 1 1 13 1 2 16 0 16 1 2 12 0 12 1 2 14 0 15 1 2 15 0 15 1 2 17 0 18 1 1 19 1 2 22 0 22 1 2 18 0 18 1 2 20 0 21 1 1 23 1 2 26 0 26 1 2 21 0 21 1 2 24 0 25 1 1 2 0 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
554090 608599
output:
48 0 2 1 0 1 1 1 2 1 2 2 0 2 1 2 3 0 4 1 1 5 1 2 8 0 8 1 2 4 0 4 1 2 6 0 7 1 1 9 1 1 10 1 2 13 0 13 1 2 14 0 14 1 2 7 0 7 1 2 11 0 12 1 2 12 0 12 1 2 15 0 16 1 2 16 0 16 1 2 17 0 18 1 1 19 1 2 22 0 22 1 2 18 0 18 1 2 20 0 21 1 1 23 1 1 24 1 1 25 1 2 28 0 28 1 2 29 0 29 1 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed