QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686033 | #9519. Build a Computer | ucup-team3294 | AC ✓ | 1ms | 3864kb | C++23 | 4.2kb | 2024-10-28 23:12:17 | 2024-10-28 23:12:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define x first
#define y second
#define endl '\n'
const int N=2e5+10;
int len(int x) {
int cnt=0;
while(x) {
x/=2;
cnt++;
}
return cnt;
}
string tos(int x) {
string s;
do {
s+=(x%2+'0');
x/=2;
} while(x);
return s;
}
void solve() {
int l,r;
int cnt=100;
cin>>l>>r;
if(l==r) {
string s=tos(l);
reverse(s.begin(),s.end());
cnt=1;
cout<<s.size()+1<<"\n";
for(int i=0; i<s.size(); i++) {
cout<<1<<" "<<cnt+1<<" "<<s[i]-'0'<<"\n";
cnt++;
}
cout<<"0\n";
return;
}
vector<PII>G[101];
for(int i=19; i>1; i--) {
G[i].push_back({i-1,0});
G[i].push_back({i-1,1});
}
int len1=len(l),len2=len(r);
for(int i=len1+1; i<len2; i++) {
G[100].push_back({i,1});
}
if(len1!=len2) {
string s;
s=tos(l);
s=" "+s;
if(l!=1) G[100].push_back({--cnt,1});
else G[100].push_back({1,1});
for(int i=len1-1; i>=1; i--) {
if(i==1) {
G[cnt].push_back({i,1});
if(s[i]-'0'==0) G[cnt].push_back({i,0});
} else if(s[i]=='0') {
G[cnt].push_back({i,1});
G[cnt].push_back({cnt-1,0});
cnt--;
} else {
G[cnt].push_back({cnt-1,1});
cnt--;
}
}
s=tos(r);
s=" "+s;
G[100].push_back({--cnt,1});
for(int i=len2-1; i>=1; i--) {
if(i==1) {
G[cnt].push_back({i,0});
if(s[i]-'0') G[cnt].push_back({i,1});
} else if(s[i]=='1') {
G[cnt].push_back({i,0});
G[cnt].push_back({cnt-1,1});
cnt--;
} else {
G[cnt].push_back({cnt-1,0});
cnt--;
}
}
} else {
string s1=tos(l),s2=tos(r);
s1=" "+s1;
s2=" "+s2;
int f1=99,f2=98;
G[100].push_back({99,1});
G[100].push_back({98,1});
cnt=98;
for(int i=len1-1; i>=1; i--) {
if(i==1) {
G[f1].push_back({1,s1[i]-'0'});
G[f2].push_back({1,s2[i]-'0'});
break;
}
G[f1].push_back({cnt-1,s1[i]-'0'});
cnt--;
f1=cnt;
G[f2].push_back({cnt-1,s2[i]-'0'});
cnt--;
f2=cnt;
if(s1[i]!=s2[i]) {
for(int j=i-1; j>=1; j--) {
if(j==1) {
G[f1].push_back({j,1});
if(s1[j]-'0'==0) G[f1].push_back({j,0});
} else if(s1[j]=='0') {
G[f1].push_back({j,1});
G[f1].push_back({--cnt,0});
f1=cnt;
} else {
G[f1].push_back({--cnt,1});
f1=cnt;
}
}
for(int j=i-1; j>=1; j--) {
if(j==1) {
G[f2].push_back({j,0});
if(s2[j]-'0') G[f2].push_back({j,1});
} else if(s2[j]=='1') {
G[f2].push_back({j,0});
G[f2].push_back({cnt-1,1});
cnt--;
f2=cnt;
} else {
G[f2].push_back({cnt-1,0});
cnt--;
f2=cnt;
}
}
break;
}
}
}
queue<int> q;
q.push(100);
vector<int> mp(200);
vector<int> mmp(200);
int k=0;
vector<int> vis(200);
vis[100]=1;
int t=-1;
for(int i=1;i<=100;i++){
if(G[i].size()){
for(auto t:G[i]){
//cout<<i<<" "<<t.x<<" "<<t.y<<endl;
}
}
}
vector<int> b;
b.push_back(100);
while(q.size()) {
int u=q.front();
q.pop();
for(auto v:G[u]) {
//cout<<u<<" "<<v.x<<endl;
if(vis[v.x]) continue;
vis[v.x]=1;
q.push(v.x);
//cout<<k<<" "<<v.x<<endl;
b.push_back(v.x);
}
}
sort(b.begin(),b.end(),greater<int>());
for(int i=0; i<b.size(); i++) {
mp[++k]=b[i];
mmp[b[i]]=k;
}
cout<<k<<"\n";
vector<int> in(200);
for(int i=1; i<=k; i++) {
//cout<<i<<" "<<mp[i]<<endl;
cout<<G[mp[i]].size()<<" ";
for(auto t:G[mp[i]]) {
in[mmp[t.x]]++;
cout<<mmp[t.x]<<" "<<t.y<<" ";
}
cout<<"\n";
}
// queue<PII> Q;
// Q.push({1,0});
// map<int,int> MP;
// while(Q.size()) {
// PII u=Q.front();
// Q.pop();
// for(auto t:G[mp[u.x]]) {
// int x=u.y*2+t.y;
//// cout<<t.x<<" "<<mmp[t.x]<<endl;
// if(mmp[t.x]==k) {
// if(x<l||x>r) {
// cout<<"No";
// return;
// }
// MP[x]++;
// //cout<<x<<endl;
// }
// Q.push({mmp[t.x],x});
// }
// }
// for(int i=l; i<=r; i++) {
// if(MP[i]!=1) {
// cout<<"No";
// return;
// }
// }
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3640kb
input:
5 7
output:
6 2 2 1 3 1 1 4 0 1 5 1 1 6 1 2 6 0 6 1 0
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
10 27
output:
12 2 2 1 5 1 2 10 1 3 0 1 4 1 2 12 1 12 0 2 9 0 6 1 1 7 0 2 11 0 8 1 2 12 0 12 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
5 13
output:
9 2 2 1 4 1 2 8 1 3 0 1 9 1 2 7 0 5 1 1 6 0 2 9 0 9 1 2 8 0 8 1 2 9 0 9 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
1 1000000
output:
39 20 38 1 37 1 36 1 35 1 34 1 33 1 32 1 31 1 30 1 29 1 28 1 27 1 26 1 25 1 24 1 23 1 22 1 21 1 39 1 2 1 2 21 0 3 1 2 22 0 4 1 2 23 0 5 1 1 6 0 2 25 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 33 0 15 1 1 16 0 1 17 0 1 18 0 1 19 0 1 20 0 1 39 0 2 22 0 22 1 2 23 0...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
7 9
output:
7 2 2 1 4 1 1 3 1 1 7 1 1 5 0 1 6 0 2 7 0 7 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
3 7
output:
6 2 2 1 3 1 1 6 1 2 5 0 4 1 2 6 0 6 1 2 6 0 6 1 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1 5
output:
5 3 4 1 5 1 2 1 1 3 0 2 5 0 5 1 2 5 0 5 1 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 4
output:
5 3 4 1 5 1 2 1 1 3 0 1 5 0 2 5 0 5 1 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
8 9
output:
8 2 2 1 3 1 1 4 0 1 5 0 1 6 0 1 7 0 1 8 0 1 8 1 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
7 51
output:
13 4 10 1 9 1 2 1 4 1 1 3 1 1 13 1 2 9 0 5 1 1 6 0 1 7 0 2 12 0 8 1 2 13 0 13 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
51 79
output:
16 2 2 1 7 1 1 3 1 2 13 1 4 0 2 14 1 5 0 1 6 1 1 16 1 1 8 0 1 9 0 2 13 0 10 1 2 14 0 11 1 2 15 0 12 1 2 16 0 16 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
92 99
output:
15 2 2 1 3 1 1 4 0 1 5 1 1 6 1 1 10 0 1 7 1 1 8 1 2 14 1 9 0 2 15 1 15 0 1 11 0 1 12 0 2 14 0 13 1 2 15 0 15 1 2 15 0 15 1 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
27 36
output:
13 2 2 1 6 1 1 3 1 2 11 1 4 0 1 5 1 1 13 1 1 7 0 1 8 0 2 11 0 9 1 1 10 0 1 13 0 2 12 0 12 1 2 13 0 13 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
55 84
output:
17 2 2 1 7 1 1 3 1 2 14 1 4 0 1 5 1 1 6 1 1 17 1 1 8 0 2 13 0 9 1 1 10 0 2 15 0 11 1 1 12 0 1 17 0 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
297208 929600
output:
57 2 2 1 20 1 2 40 1 3 0 2 41 1 4 0 1 5 1 2 43 1 6 0 2 44 1 7 0 2 45 1 8 0 1 9 1 2 47 1 10 0 2 48 1 11 0 2 49 1 12 0 1 13 1 1 14 1 1 15 1 1 16 1 1 17 1 2 55 1 18 0 2 56 1 19 0 2 57 1 57 0 2 39 0 21 1 2 40 0 22 1 1 23 0 1 24 0 1 25 0 2 44 0 26 1 1 27 0 2 46 0 28 1 2 47 0 29...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
45728 589156
output:
54 5 38 1 37 1 36 1 2 1 17 1 2 40 1 3 0 1 4 1 1 5 1 2 43 1 6 0 2 44 1 7 0 1 8 1 2 46 1 9 0 1 10 1 2 48 1 11 0 1 12 1 2 50 1 13 0 2 51 1 14 0 2 52 1 15 0 2 53 1 16 0 2 54 1 54 0 1 18 0 1 19 0 1 20 0 2 39 0 21 1 2 40 0 22 1 2 41 0 23 1 2 42 0 24 1 2 43 0 25 1 2 44 0 26 1 1 27 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
129152 138000
output:
47 2 2 1 18 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 2 37 1 8 0 2 38 1 9 0 2 39 1 10 0 1 11 1 2 41 1 12 0 2 42 1 13 0 2 43 1 14 0 2 44 1 15 0 2 45 1 16 0 2 46 1 17 0 2 47 1 47 0 1 19 0 1 20 0 1 21 0 1 22 0 2 35 0 23 1 2 36 0 24 1 1 25 0 2 38 0 26 1 2 39 0 27 1 1 28 0 1 29 0 1 30 0...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
245280 654141
output:
56 3 38 1 2 1 19 1 1 3 1 1 4 1 2 42 1 5 0 1 6 1 1 7 1 1 8 1 1 9 1 1 10 1 2 48 1 11 0 2 49 1 12 0 2 50 1 13 0 1 14 1 2 52 1 15 0 2 53 1 16 0 2 54 1 17 0 2 55 1 18 0 2 56 1 56 0 1 20 0 1 21 0 2 40 0 22 1 2 41 0 23 1 2 42 0 24 1 2 43 0 25 1 2 44 0 26 1 2 45 0 27 1 1 28 0 2 47...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
202985 296000
output:
52 2 2 1 19 1 1 3 1 2 37 1 4 0 2 38 1 5 0 2 39 1 6 0 1 7 1 1 8 1 2 42 1 9 0 2 43 1 10 0 2 44 1 11 0 1 12 1 1 13 1 1 14 1 2 48 1 15 0 1 16 1 2 50 1 17 0 2 51 1 18 0 1 52 1 1 20 0 1 21 0 2 37 0 22 1 1 23 0 1 24 0 1 25 0 1 26 0 2 42 0 27 1 1 28 0 1 29 0 1 30 0 2 46 0 31 1 ...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
438671 951305
output:
57 2 2 1 20 1 1 3 1 2 41 1 4 0 1 5 1 2 43 1 6 0 1 7 1 1 8 1 2 46 1 9 0 2 47 1 10 0 2 48 1 11 0 1 12 1 1 13 1 2 51 1 14 0 2 52 1 15 0 2 53 1 16 0 1 17 1 1 18 1 1 19 1 1 57 1 2 39 0 21 1 2 40 0 22 1 1 23 0 2 42 0 24 1 1 25 0 1 26 0 1 27 0 1 28 0 2 47 0 29 1 1 30 0 1 31 0 ...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
425249 739633
output:
56 2 2 1 20 1 1 3 1 2 40 1 4 0 2 41 1 5 0 1 6 1 1 7 1 1 8 1 1 9 1 1 10 1 2 47 1 11 0 1 12 1 2 49 1 13 0 2 50 1 14 0 1 15 1 2 52 1 16 0 2 53 1 17 0 2 54 1 18 0 2 55 1 19 0 1 56 1 1 21 0 2 39 0 22 1 2 40 0 23 1 1 24 0 2 42 0 25 1 1 26 0 1 27 0 2 45 0 28 1 1 29 0 1 30 0 2 4...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
551207 961718
output:
57 2 2 1 3 1 1 4 0 1 5 1 2 40 1 6 0 2 40 0 23 1 2 41 1 7 0 2 42 1 8 0 1 9 1 1 10 1 2 45 1 11 0 1 12 1 2 47 1 13 0 2 48 1 14 0 1 15 1 2 50 1 16 0 2 51 1 17 0 1 18 1 2 53 1 19 0 2 54 1 20 0 1 21 1 1 22 1 1 57 1 1 24 0 2 42 0 25 1 1 26 0 2 44 0 27 1 1 28 0 2 46 0 29 1 2 47 0...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
114691 598186
output:
55 4 38 1 37 1 2 1 18 1 1 3 1 1 4 1 2 42 1 5 0 2 43 1 6 0 2 44 1 7 0 2 45 1 8 0 2 46 1 9 0 2 47 1 10 0 2 48 1 11 0 2 49 1 12 0 2 50 1 13 0 2 51 1 14 0 2 52 1 15 0 2 53 1 16 0 1 17 1 1 55 1 1 19 0 1 20 0 2 39 0 21 1 1 22 0 1 23 0 2 42 0 24 1 1 25 0 1 26 0 1 27 0 1 28 0 1 29...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
234654 253129
output:
49 2 2 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 8 0 1 9 1 2 36 1 10 0 1 23 0 1 11 1 2 38 1 12 0 1 13 1 2 40 1 14 0 2 41 1 15 0 1 16 1 2 43 1 17 0 2 44 1 18 0 1 19 1 1 20 1 1 21 1 1 22 1 2 49 1 49 0 2 37 0 24 1 2 38 0 25 1 2 39 0 26 1 1 27 0 1 28 0 2 42 0 29 1 2 43 0 30 1 1 31 0 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
554090 608599
output:
55 2 2 1 3 1 1 4 0 1 5 0 1 6 0 1 7 0 1 8 0 1 9 1 2 40 1 10 0 1 25 0 1 11 1 1 12 1 1 13 1 2 44 1 14 0 1 15 1 2 46 1 16 0 2 47 1 17 0 2 48 1 18 0 1 19 1 1 20 1 2 51 1 21 0 1 22 1 2 53 1 23 0 1 24 1 2 55 1 55 0 2 41 0 26 1 1 27 0 1 28 0 2 44 0 29 1 1 30 0 1 31 0 2 47 0 32 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed