QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694808 | #9519. Build a Computer | emt | AC ✓ | 0ms | 3936kb | C++20 | 2.9kb | 2024-10-31 18:42:21 | 2024-10-31 18:42:40 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
using i128 = __int128_t;
using u128 = __uint128_t;
using ld = long double;
using i64 = long long;
using pi = pair<int,int>;
#define mem(a, b) memset((a), (b), sizeof(a))
#define all(a) (a).begin(), (a).end()
#define lowbit(x) (-x)&x
#define ls u<<1
#define rs u<<1|1
mt19937 rnd(time(0));
const i64 mod = 998244353;
const i64 N = 1e3+7;
const i64 inf = 1e18+7;
i64 qmi(i64 m, i128 k,i64 p = mod){i128 res = 1, t = m;while (k){if (k & 1) res = (res * t) % p;t = t * t % p;k >>= 1;}return res;}
i64 inv(i64 u){return qmi(u,mod-2);}
void solve()
{
int n = 1;
vector<array<int,2>> G(101);
vector g(101,vector<vector<int>>(2));
int l,r;cin>>l>>r;
int nowl = l, nowr = r;
auto lowbi = [](int x){
return lowbit(x);
};
vector<array<int,2>> res,res2;
while(1)
{
int nx = nowl - 1 + lowbi(nowl);
if(nx>r) break;
res.push_back({nowl,nx});
nowl = nx+1;
}
while(1)
{
int nx = nowr - lowbi(nowr);
if(nx==0 || nx<nowl) break;
res2.push_back({nx,nowr-1});
nowr -= lowbi(nowr);
}
if(nowl<=r) res.push_back({r,r});
reverse(all(res2));
for(auto c:res2)
res.push_back(c);
// for(auto [c,d]:res)
// cout<<"$"<<c<<" "<<d<<"\n";
vector<array<int,3>> ne;
int maxne = 0;
auto link = [&](int st, int final,int dest){
string rt = bitset<21>(st).to_string();
reverse(all(rt));
while(rt.back()=='0') rt.pop_back();
reverse(all(rt));
int sta = 1;
for(auto c:rt)
{
if(!G[sta][c-'0'])
G[sta][c-'0'] = ++n;
sta = G[sta][c-'0'];
}
ne.push_back({sta,final,dest});
// G[sta][final] = dest;
maxne = max(dest,maxne);
};
// for(int i=2;i<=20;i++)
// G[i][0] = G[i][1] = i-1;
for(auto [c,d]:res)
{
int p = d-c;
int dest = 1;
while(p) dest++,p>>=1;
link(c>>dest, (c>>(dest-1))&1, dest);
}
cout<<n+maxne<<"\n";
for(int i=n+2;i<=maxne+n;i++)
G[i][1] = G[i][0] = i-1;
for(auto [c,d,e]:ne)
g[c][d].push_back(e+n);
for(int i=1;i<=n+maxne;i++)
{
vector<array<int,2>> pp;
for(int j=0;j<2;j++)
{
if(G[i][j])
pp.push_back({G[i][j],j});
for(auto c:g[i][j])
pp.push_back({c,j});
}
cout<<pp.size();
for(auto [c,d]:pp) cout<<" "<<c<<" "<<d;
cout<<"\n";
}
}
signed main()
{
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;
// cin>>T;
while(T--) solve();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
5 7
output:
5 1 2 1 2 3 0 5 1 1 4 1 0 2 4 0 4 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
10 27
output:
10 1 2 1 4 3 0 10 0 4 1 9 1 1 8 1 1 5 0 2 8 0 6 1 2 7 0 7 1 0 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
5 13
output:
8 1 2 1 4 3 0 8 0 4 1 7 1 1 6 1 1 5 0 2 6 0 6 1 0 2 6 0 6 1 2 7 0 7 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
1 1000000
output:
39 20 2 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 2 39 0 3 1 2 38 0 4 1 2 37 0 5 1 1 6 0 2 35 0 7 1 1 8 0 1 9 0 1 10 0 1 11 0 2 30 0 12 1 1 13 0 1 14 0 2 27 0 15 1 1 16 0 1 17 0 1 18 0 1 19 0 1 20 0 1 21 0 0 2 21 0 21 1 2 22 0 22 1 2 23 0 23 1 2...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
7 9
output:
6 1 2 1 2 4 0 3 1 1 6 1 1 5 0 2 6 0 6 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
3 7
output:
5 2 2 1 5 1 1 3 1 0 2 3 0 3 1 2 4 0 4 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
1 5
output:
5 3 2 1 4 1 5 1 1 3 0 2 4 0 4 1 0 2 4 0 4 1
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1 4
output:
5 3 2 1 4 1 5 1 1 3 0 1 4 0 0 2 4 0 4 1
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
8 9
output:
5 1 2 1 1 3 0 1 4 0 2 5 0 5 1 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
7 51
output:
11 3 2 1 10 1 11 1 2 11 0 3 1 2 4 0 7 1 1 5 0 2 8 0 6 1 2 7 0 7 1 0 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
51 79
output:
15 1 2 1 2 7 0 3 1 2 4 0 15 1 2 5 0 14 1 1 6 1 1 12 1 1 8 0 2 15 0 9 1 2 14 0 10 1 2 13 0 11 1 2 12 0 12 1 0 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
92 99
output:
13 1 2 1 2 3 0 6 1 1 4 1 1 5 1 1 13 1 1 7 0 1 8 0 1 9 0 2 12 0 10 1 2 11 0 11 1 0 2 11 0 11 1 2 12 0 12 1
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
27 36
output:
12 1 2 1 2 6 0 3 1 2 4 0 12 1 1 5 1 1 10 1 1 7 0 2 12 0 8 1 1 9 0 1 10 0 0 2 10 0 10 1 2 11 0 11 1
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
55 84
output:
16 1 2 1 2 7 0 3 1 2 4 0 15 1 1 5 1 1 6 1 1 12 1 2 16 0 8 1 1 9 0 2 14 0 10 1 1 11 0 1 12 0 0 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
297208 929600
output:
53 1 2 1 4 3 0 53 0 17 1 52 1 2 4 0 51 1 1 5 1 2 6 0 49 1 2 7 0 48 1 2 8 0 47 1 1 9 1 2 10 0 45 1 2 11 0 44 1 2 12 0 43 1 1 13 1 1 14 1 1 15 1 1 16 1 1 38 1 2 52 0 18 1 1 19 0 1 20 0 1 21 0 2 48 0 22 1 1 23 0 2 46 0 24 1 2 45 0 25 1 2 44 0 26 1 2 43 0 27 1 1 28 0 2 41 0 29 1 1 30 0 1 31 0 1 32 0 1 3...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
45728 589156
output:
47 4 2 1 45 1 46 1 47 1 2 3 0 43 1 2 12 0 4 1 1 5 1 2 6 0 40 1 2 7 0 39 1 1 8 1 2 9 0 37 1 1 10 1 2 11 0 35 1 1 34 1 1 13 0 2 44 0 14 1 2 43 0 15 1 2 42 0 16 1 2 41 0 17 1 2 40 0 18 1 2 39 0 19 1 1 20 0 2 37 0 21 1 1 22 0 2 35 0 23 1 2 34 0 24 1 1 25 0 1 26 0 2 31 0 27 1 1 28 0 1 29 0 0 2 29 0 29 1 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
129152 138000
output:
39 1 2 1 2 11 0 3 1 1 4 1 1 5 1 1 6 1 1 7 1 2 8 0 37 1 2 9 0 36 1 2 10 0 35 1 1 34 1 1 12 0 1 13 0 1 14 0 2 39 0 15 1 2 38 0 16 1 1 17 0 2 36 0 18 1 2 35 0 19 1 1 20 0 1 21 0 1 22 0 2 31 0 23 1 1 24 0 1 25 0 1 26 0 1 27 0 0 2 27 0 27 1 2 28 0 28 1 2 29 0 29 1 2 30 0 30 1 2 31 0 31 1 2 32 0 32 1 2 33...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
245280 654141
output:
50 2 2 1 50 1 2 14 0 3 1 1 4 1 2 5 0 46 1 1 6 1 1 7 1 1 8 1 1 9 1 1 10 1 2 11 0 40 1 2 12 0 39 1 2 13 0 38 1 1 37 1 1 15 0 2 48 0 16 1 2 47 0 17 1 2 46 0 18 1 2 45 0 19 1 2 44 0 20 1 2 43 0 21 1 1 22 0 2 41 0 23 1 2 40 0 24 1 1 25 0 1 26 0 2 37 0 27 1 2 36 0 28 1 2 35 0 29 1 2 34 0 30 1 1 31 0 2 32 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
202985 296000
output:
51 1 2 1 2 19 0 3 1 2 4 0 51 1 2 5 0 50 1 2 6 0 49 1 1 7 1 1 8 1 2 9 0 46 1 2 10 0 45 1 2 11 0 44 1 1 12 1 1 13 1 1 14 1 2 15 0 40 1 1 16 1 2 17 0 38 1 2 18 0 37 1 1 36 1 1 20 0 2 51 0 21 1 1 22 0 1 23 0 1 24 0 1 25 0 2 46 0 26 1 1 27 0 1 28 0 1 29 0 2 42 0 30 1 1 31 0 1 32 0 1 33 0 1 34 0 1 35 0 1 ...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
438671 951305
output:
55 1 2 1 2 55 0 3 1 4 4 0 54 0 20 1 53 1 1 5 1 2 6 0 51 1 1 7 1 1 8 1 2 9 0 48 1 2 10 0 47 1 2 11 0 46 1 1 12 1 1 13 1 2 14 0 43 1 2 15 0 42 1 2 16 0 41 1 1 17 1 1 18 1 1 19 1 1 37 1 1 21 0 2 52 0 22 1 1 23 0 1 24 0 1 25 0 1 26 0 2 47 0 27 1 1 28 0 1 29 0 1 30 0 1 31 0 1 32 0 1 33 0 2 40 0 34 1 1 35...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
425249 739633
output:
55 1 2 1 2 20 0 3 1 2 4 0 54 1 2 5 0 53 1 1 6 1 1 7 1 1 8 1 1 9 1 1 10 1 2 11 0 47 1 1 12 1 2 13 0 45 1 2 14 0 44 1 1 15 1 2 16 0 42 1 2 17 0 41 1 2 18 0 40 1 2 19 0 39 1 1 38 1 2 55 0 21 1 2 54 0 22 1 1 23 0 2 52 0 24 1 1 25 0 1 26 0 2 49 0 27 1 1 28 0 1 29 0 2 46 0 30 1 1 31 0 1 32 0 2 43 0 33 1 2...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
551207 961718
output:
56 1 2 1 2 3 0 21 1 2 4 0 56 1 2 5 0 55 1 2 6 0 54 1 1 7 1 1 8 1 2 9 0 51 1 1 10 1 2 11 0 49 1 2 12 0 48 1 1 13 1 2 14 0 46 1 2 15 0 45 1 1 16 1 2 17 0 43 1 2 18 0 42 1 1 19 1 1 20 1 1 39 1 2 56 0 22 1 1 23 0 2 54 0 24 1 1 25 0 2 52 0 26 1 1 27 0 2 50 0 28 1 2 49 0 29 1 1 30 0 1 31 0 2 46 0 32 1 1 3...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
114691 598186
output:
54 3 2 1 53 1 54 1 2 18 0 3 1 1 4 1 2 5 0 49 1 2 6 0 48 1 2 7 0 47 1 2 8 0 46 1 2 9 0 45 1 2 10 0 44 1 2 11 0 43 1 2 12 0 42 1 2 13 0 41 1 2 14 0 40 1 2 15 0 39 1 2 16 0 38 1 1 17 1 1 36 1 1 19 0 2 52 0 20 1 1 21 0 1 22 0 2 49 0 23 1 1 24 0 1 25 0 1 26 0 1 27 0 1 28 0 2 43 0 29 1 1 30 0 2 41 0 31 1 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
234654 253129
output:
45 1 2 1 1 3 1 1 4 1 2 5 0 18 1 2 6 0 45 1 1 7 1 2 8 0 43 1 1 9 1 2 10 0 41 1 2 11 0 40 1 1 12 1 2 13 0 38 1 2 14 0 37 1 1 15 1 1 16 1 1 17 1 1 33 1 1 19 0 2 44 0 20 1 2 43 0 21 1 2 42 0 22 1 1 23 0 1 24 0 2 39 0 25 1 2 38 0 26 1 1 27 0 1 28 0 2 35 0 29 1 1 30 0 1 31 0 2 32 0 32 1 0 2 32 0 32 1 2 33...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
554090 608599
output:
51 1 2 1 1 3 0 1 4 0 2 5 0 20 1 2 6 0 51 1 1 7 1 1 8 1 1 9 1 2 10 0 47 1 1 11 1 2 12 0 45 1 2 13 0 44 1 2 14 0 43 1 1 15 1 1 16 1 2 17 0 40 1 1 18 1 2 19 0 38 1 1 37 1 1 21 0 2 50 0 22 1 1 23 0 1 24 0 2 47 0 25 1 1 26 0 1 27 0 2 44 0 28 1 1 29 0 2 42 0 30 1 1 31 0 2 40 0 32 1 1 33 0 2 38 0 34 1 2 37...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed