QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#681368 | #9519. Build a Computer | ucup-team5141# | AC ✓ | 0ms | 3800kb | C++23 | 3.0kb | 2024-10-27 05:58:51 | 2024-10-27 05:58:52 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define ld long double
using namespace std;
vector<pair<int, int> > adj[500];
int currentNode = 1;
int easyPath[50];
void addEdje(int u, int v, int value){
if(v == -1)return ;
adj[u].pb({v, value});
}
int calc_easy_path(int pot){
//cout << "calc easy " << pot << endl;
if(pot == 0)return 200;
if(easyPath[pot] != -1){
return easyPath[pot];
}
easyPath[pot] = currentNode ++ ;
addEdje(easyPath[pot], calc_easy_path(pot-1), 1);
addEdje(easyPath[pot], calc_easy_path(pot-1), 0);
return easyPath[pot];
}
int solve(int l, int r, int currentBit){
//cout << "solving " << l << " " << r << endl;
if(l > r)return -1;
if(currentBit == -1){
return 200;
}
if(l == 0 && (r == (1 << (currentBit + 1) ) - 1)){
return calc_easy_path(currentBit + 1);
}
int on = (1 << currentBit);
int u = currentNode ++ ;
int resultNode = solve(max(0, l - on), r - on, currentBit - 1);
if(resultNode != -1){
addEdje(u, resultNode, 1);
}
resultNode = solve(l, min(r, on - 1), currentBit - 1);
if(resultNode != -1){
addEdje(u, resultNode, 0);
}
return u;
}
int try_solve(int l, int r){
vector<int>insides;
for(int on_bit = 0 ; on_bit < 30 ; on_bit ++ ){
int curPot = (1 << on_bit);
if(curPot >= l && curPot <= r){
insides.pb(on_bit);
}
}
int inicio = currentNode ++ ;
if(insides.empty()){
for(int bit = 29 ; bit >= 0 ; bit --){
int on = (1 << bit);
if((on & l) && (on & r)){
addEdje(inicio, solve(l - on, r - on, bit - 1), 1);
return inicio;
}
}
return inicio;
}
addEdje(inicio, solve(0, r - (1 << insides.back()), insides.back() - 1), 1);
int bitt = (insides[0] - 1); // What if insides[0] == 0?
if(bitt != -1){
addEdje(inicio, solve(l - (1 << bitt), (1 << insides[0] ) - 1 - (1 << bitt), bitt - 1), 1);
}
for(int i = 0 ; i < (int)insides.size() - 1 ; ++ i){
int from = (1 << insides[i]) - (1 << insides[i]); // 10000 -> 00000,
int upto = (1 << insides[i+1]) - 1 - (1 << insides[i]);
addEdje(inicio, solve(from, upto, insides[i] - 1), 1);
}
return inicio;
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
int l, r;
cin >> l >> r;
memset(easyPath, -1, sizeof easyPath);
try_solve(l, r);
cout << currentNode << "\n";
for(int i = 1 ; i <= currentNode ; i ++){
cout << adj[i].size() << " ";
for(int j = 0 ; j < adj[i].size() ; j ++){
if(adj[i][j].ff == 200)adj[i][j].ff = currentNode;
cout << adj[i][j].ff << " " << adj[i][j].ss << " ";
}
cout << "\n";
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
5 7
output:
5 1 2 1 2 3 1 4 0 2 5 1 5 0 1 5 1 0
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
10 27
output:
9 2 2 1 7 1 2 3 1 6 0 1 4 0 2 5 1 5 0 2 9 1 9 0 2 4 1 4 0 2 4 1 8 0 1 5 1 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
5 13
output:
8 2 2 1 6 1 2 3 1 5 0 1 4 0 2 8 1 8 0 2 4 1 4 0 2 4 1 7 0 1 8 1 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
1 1000000
output:
39 20 2 1 39 1 26 1 25 1 24 1 23 1 22 1 21 1 29 1 28 1 27 1 34 1 33 1 32 1 31 1 30 1 36 1 35 1 37 1 38 1 2 3 1 38 0 2 4 1 37 0 2 5 1 35 0 1 6 0 2 7 1 30 0 1 8 0 1 9 0 1 10 0 1 11 0 2 12 1 27 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 39 0 2 22 1 22 0 2 23 1...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
7 9
output:
7 2 2 1 5 1 1 3 0 1 4 0 2 7 1 7 0 1 6 1 1 7 1 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
3 7
output:
5 2 2 1 4 1 2 3 1 3 0 2 5 1 5 0 1 5 1 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1 5
output:
4 3 2 1 4 1 3 1 1 3 0 2 4 1 4 0 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 4
output:
5 3 2 1 5 1 4 1 1 3 0 1 5 0 2 5 1 5 0 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
8 9
output:
5 1 2 1 1 3 0 1 4 0 2 5 1 5 0 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
7 51
output:
11 4 2 1 9 1 8 1 7 1 2 3 1 7 0 1 4 0 1 5 0 2 6 1 6 0 2 11 1 11 0 2 8 1 8 0 2 5 1 5 0 1 10 1 1 11 1 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
51 79
output:
13 2 2 1 8 1 1 3 0 1 4 0 2 5 1 5 0 2 6 1 6 0 2 7 1 7 0 2 13 1 13 0 1 9 1 2 5 1 10 0 2 6 1 11 0 1 12 1 1 13 1 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
92 99
output:
11 1 2 1 2 3 1 8 0 1 4 0 1 5 0 1 6 0 2 7 1 7 0 2 11 1 11 0 1 9 1 1 10 1 1 6 1 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
27 36
output:
13 2 2 1 9 1 1 3 0 1 4 0 2 5 1 7 0 1 6 0 1 13 0 2 8 1 8 0 2 13 1 13 0 1 10 1 2 7 1 11 0 1 12 1 1 13 1 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
55 84
output:
17 2 2 1 12 1 1 3 0 2 4 1 10 0 1 5 0 2 6 1 8 0 1 7 0 1 17 0 2 9 1 9 0 2 17 1 17 0 2 11 1 11 0 2 8 1 8 0 1 13 1 2 11 1 14 0 1 15 1 1 16 1 1 17 1 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
297208 929600
output:
54 2 2 1 39 1 2 3 1 38 0 2 4 1 34 0 1 5 0 1 6 0 1 7 0 2 8 1 32 0 1 9 0 2 10 1 31 0 2 11 1 30 0 2 12 1 29 0 2 13 1 27 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 54 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 54 1 54 0 2 28 1 28 0 2 21 1 21...
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
45728 589156
output:
49 5 2 1 36 1 46 1 47 1 48 1 1 3 0 1 4 0 1 5 0 2 6 1 35 0 2 7 1 34 0 2 8 1 33 0 2 9 1 32 0 2 10 1 31 0 2 11 1 29 0 1 12 0 2 13 1 27 0 1 14 0 2 15 1 26 0 2 16 1 23 0 1 17 0 1 18 0 2 19 1 21 0 1 20 0 1 49 0 2 22 1 22 0 2 49 1 49 0 2 24 1 24 0 2 25 1 25 0 2 21 1 21 0 2 23 1 23 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
129152 138000
output:
40 2 2 1 31 1 1 3 0 1 4 0 1 5 0 1 6 0 2 7 1 30 0 2 8 1 28 0 1 9 0 2 10 1 27 0 2 11 1 23 0 1 12 0 1 13 0 1 14 0 2 15 1 19 0 1 16 0 1 17 0 1 18 0 1 40 0 2 20 1 20 0 2 21 1 21 0 2 22 1 22 0 2 40 1 40 0 2 24 1 24 0 2 25 1 25 0 2 26 1 26 0 2 19 1 19 0 2 23 1 23 0 2 29 1 29 0 2...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
245280 654141
output:
50 3 2 1 36 1 48 1 1 3 0 1 4 0 2 5 1 35 0 2 6 1 34 0 2 7 1 33 0 2 8 1 32 0 2 9 1 31 0 2 10 1 29 0 1 11 0 2 12 1 28 0 2 13 1 25 0 1 14 0 1 15 0 2 16 1 24 0 2 17 1 23 0 2 18 1 22 0 2 19 1 21 0 1 20 0 2 50 1 50 0 2 20 1 20 0 2 21 1 21 0 2 22 1 22 0 2 23 1 23 0 2 26 1 26 0 2 27 ...
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
202985 296000
output:
52 2 2 1 35 1 1 3 0 1 4 0 2 5 1 30 0 1 6 0 1 7 0 1 8 0 1 9 0 2 10 1 26 0 1 11 0 1 12 0 1 13 0 2 14 1 20 0 1 15 0 1 16 0 1 17 0 1 18 0 1 19 0 1 52 0 2 21 1 21 0 2 22 1 22 0 2 23 1 23 0 2 24 1 24 0 2 25 1 25 0 2 52 1 52 0 2 27 1 27 0 2 28 1 28 0 2 29 1 29 0 2 20 1 20 0 2 3...
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
438671 951305
output:
56 2 2 1 38 1 2 3 1 37 0 2 4 1 35 0 1 5 0 2 6 1 30 0 1 7 0 1 8 0 1 9 0 1 10 0 2 11 1 23 0 1 12 0 1 13 0 1 14 0 1 15 0 1 16 0 1 17 0 2 18 1 21 0 1 19 0 1 20 0 2 56 1 56 0 2 22 1 22 0 2 20 1 20 0 2 24 1 24 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 21 1...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
425249 739633
output:
55 2 2 1 37 1 1 3 0 2 4 1 36 0 2 5 1 34 0 1 6 0 2 7 1 31 0 1 8 0 1 9 0 2 10 1 28 0 1 11 0 1 12 0 2 13 1 25 0 1 14 0 1 15 0 2 16 1 24 0 2 17 1 21 0 1 18 0 1 19 0 1 20 0 2 55 1 55 0 2 22 1 22 0 2 23 1 23 0 2 20 1 20 0 2 21 1 21 0 2 26 1 26 0 2 27 1 27 0 2 24 1 24 0 2 29 1 29...
result:
ok ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
551207 961718
output:
56 1 2 1 2 3 1 38 0 2 4 1 36 0 1 5 0 2 6 1 34 0 1 7 0 2 8 1 32 0 1 9 0 2 10 1 31 0 2 11 1 28 0 1 12 0 1 13 0 2 14 1 26 0 1 15 0 2 16 1 25 0 2 17 1 23 0 1 18 0 2 19 1 22 0 2 20 1 21 0 1 56 0 2 56 1 56 0 2 21 1 21 0 2 24 1 24 0 2 22 1 22 0 2 23 1 23 0 2 27 1 27 0 2 25 1 25 0 ...
result:
ok ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
114691 598186
output:
55 4 2 1 37 1 53 1 54 1 1 3 0 1 4 0 2 5 1 34 0 1 6 0 1 7 0 2 8 1 28 0 1 9 0 1 10 0 1 11 0 1 12 0 1 13 0 2 14 1 26 0 1 15 0 2 16 1 24 0 1 17 0 2 18 1 22 0 1 19 0 2 20 1 21 0 1 55 0 2 55 1 55 0 2 23 1 23 0 2 21 1 21 0 2 25 1 25 0 2 22 1 22 0 2 27 1 27 0 2 24 1 24 0 2 29 1 29...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
234654 253129
output:
44 1 2 1 1 3 1 1 4 1 2 5 1 30 0 1 6 0 2 7 1 29 0 2 8 1 28 0 2 9 1 25 0 1 10 0 1 11 0 2 12 1 24 0 2 13 1 21 0 1 14 0 1 15 0 2 16 1 19 0 1 17 0 1 18 0 2 44 1 44 0 2 20 1 20 0 2 18 1 18 0 2 22 1 22 0 2 23 1 23 0 2 19 1 19 0 2 21 1 21 0 2 26 1 26 0 2 27 1 27 0 2 24 1 24 0 2 25...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
554090 608599
output:
48 1 2 1 1 3 0 1 4 0 2 5 1 32 0 1 6 0 2 7 1 29 0 1 8 0 1 9 0 2 10 1 26 0 1 11 0 1 12 0 2 13 1 24 0 1 14 0 2 15 1 22 0 1 16 0 2 17 1 21 0 1 18 0 2 19 1 19 0 2 20 1 20 0 2 48 1 48 0 2 18 1 18 0 2 23 1 23 0 2 21 1 21 0 2 25 1 25 0 2 22 1 22 0 2 27 1 27 0 2 28 1 28 0 2 24 1 24...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed