#include "grid.h"
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define SZ(x) (int)x.size()
vector<int> SortDisks(int n) {
vector<int> rem; // remaining child indices
vector<int> ans; // length for i-th child
int rev[n]; // inverse map of ans (child with length i-1)
for(int i=0;i<n;i++){
rem.pb(i);
ans.pb(-1);
rev[i]=-1;
}
int prv=PutDisks(rem);
while(!rem.empty()){
vector<int> test;
int tmp=rem[SZ(rem)-1];
for(int i=0;i<SZ(rem);i++){
swap(tmp,rem[i]); // rightshift everything
}
int idx=0;
for(int i=0;i<n;i++){
if(rev[i]==-1)test.pb(rem[idx++]); // there is no known child with this length
else test.pb(rev[i]); // there is a known child with this length -> we want to un-bottleneck
}
int cur=PutDisks(test);
if(cur<prv){ // moving the top unknown to the bottom didnt change anything
prv=cur;
}else{ // the bottom ("length" (index in test) whose child is unknown) child can be determined
for(int b=0;b<n;b++){
if(rev[b]==-1){
// test[b]=rem[0] is the child's index
ans[rem[0]]=cur-n+b+1;
rev[ans[rem[0]]-1]=rem[0];
for(int i=0;i<SZ(rem)-1;i++){
rem[i]=rem[i+1];
}
rem.pop_back();
break;
}
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
296 KB |
Output is correct |
| 9 |
Correct |
1 ms |
292 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
2 ms |
204 KB |
Output is correct |
| 12 |
Correct |
2 ms |
292 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
3 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
2 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
296 KB |
Output is correct |
| 9 |
Correct |
1 ms |
292 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
2 ms |
204 KB |
Output is correct |
| 12 |
Correct |
2 ms |
292 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
3 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
2 ms |
204 KB |
Output is correct |
| 17 |
Correct |
3 ms |
300 KB |
Output is correct |
| 18 |
Correct |
9 ms |
204 KB |
Output is correct |
| 19 |
Correct |
10 ms |
204 KB |
Output is correct |
| 20 |
Correct |
14 ms |
320 KB |
Output is correct |
| 21 |
Correct |
6 ms |
204 KB |
Output is correct |
| 22 |
Correct |
13 ms |
324 KB |
Output is correct |
| 23 |
Correct |
14 ms |
320 KB |
Output is correct |
| 24 |
Correct |
13 ms |
328 KB |
Output is correct |
| 25 |
Correct |
14 ms |
324 KB |
Output is correct |
| 26 |
Correct |
12 ms |
324 KB |
Output is correct |
