#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vi res;
int N;
string submit;
void firstHalf(int l,int r){
if(r-l){
int m = (l+r)/2;
for(int i=0;i<N;i++){
if(i < l || i > r){
submit[i] = '1';
}
}
for(int i=l;i<=m;i++){
submit[i] = '1';
add_element(submit);
submit[i] = '0';
}
for(int i=0;i<N;i++){
if(i < l || i > r){
submit[i] = '0';
}
}
firstHalf(l,m);
firstHalf(m+1,r);
}
}
void secondHalf(int l,int r,vi used,vi unused){
if(r-l){
int m = (l+r)/2;
for(int it : unused){
submit[it] = '1';
}
vi left,right;
for(int it : used){
submit[it] = '1';
bool valid = check_element(submit);
if(valid){
left.emplace_back(it);
}else{
right.emplace_back(it);
}
submit[it] = '0';
}
for(int i=0;i<N;i++){
submit[i] = '0';
}
vi lunused = unused, runused = unused;
lunused.insert(lunused.begin(),left.begin(),left.end());
runused.insert(runused.begin(),right.begin(),right.end());
secondHalf(l,m,left,runused);
secondHalf(m+1,r,right,lunused);
}else{
res[used.back()] = l;
}
}
std::vector<int> restore_permutation(int n, int w, int r) {
N = n;
vi used,unused;
for(int i=0;i<N;i++){
res.emplace_back(i);
submit.push_back('0');
used.emplace_back(i);
}
firstHalf(0,N-1);
compile_set();
secondHalf(0,N-1,used,unused);
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
n = 8 |
2 |
Correct |
0 ms |
212 KB |
n = 8 |
3 |
Correct |
0 ms |
212 KB |
n = 8 |
4 |
Correct |
0 ms |
212 KB |
n = 8 |
5 |
Correct |
0 ms |
212 KB |
n = 8 |
6 |
Correct |
0 ms |
212 KB |
n = 8 |
7 |
Correct |
1 ms |
212 KB |
n = 8 |
8 |
Correct |
0 ms |
212 KB |
n = 8 |
9 |
Correct |
0 ms |
212 KB |
n = 8 |
10 |
Correct |
0 ms |
212 KB |
n = 8 |
11 |
Correct |
1 ms |
212 KB |
n = 8 |
12 |
Correct |
0 ms |
212 KB |
n = 8 |
13 |
Correct |
0 ms |
212 KB |
n = 8 |
14 |
Correct |
0 ms |
212 KB |
n = 8 |
15 |
Correct |
0 ms |
212 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 32 |
2 |
Correct |
1 ms |
212 KB |
n = 32 |
3 |
Correct |
1 ms |
212 KB |
n = 32 |
4 |
Correct |
1 ms |
212 KB |
n = 32 |
5 |
Correct |
1 ms |
296 KB |
n = 32 |
6 |
Correct |
1 ms |
212 KB |
n = 32 |
7 |
Correct |
1 ms |
212 KB |
n = 32 |
8 |
Correct |
1 ms |
212 KB |
n = 32 |
9 |
Correct |
1 ms |
296 KB |
n = 32 |
10 |
Correct |
1 ms |
296 KB |
n = 32 |
11 |
Correct |
1 ms |
300 KB |
n = 32 |
12 |
Correct |
1 ms |
296 KB |
n = 32 |
13 |
Correct |
1 ms |
212 KB |
n = 32 |
14 |
Correct |
1 ms |
212 KB |
n = 32 |
15 |
Correct |
1 ms |
212 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 32 |
2 |
Correct |
1 ms |
212 KB |
n = 32 |
3 |
Correct |
0 ms |
212 KB |
n = 32 |
4 |
Correct |
1 ms |
212 KB |
n = 32 |
5 |
Correct |
1 ms |
212 KB |
n = 32 |
6 |
Correct |
1 ms |
300 KB |
n = 32 |
7 |
Correct |
1 ms |
212 KB |
n = 32 |
8 |
Correct |
0 ms |
212 KB |
n = 32 |
9 |
Correct |
1 ms |
292 KB |
n = 32 |
10 |
Correct |
1 ms |
212 KB |
n = 32 |
11 |
Correct |
1 ms |
212 KB |
n = 32 |
12 |
Correct |
1 ms |
212 KB |
n = 32 |
13 |
Correct |
1 ms |
212 KB |
n = 32 |
14 |
Correct |
1 ms |
212 KB |
n = 32 |
15 |
Correct |
1 ms |
212 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
n = 128 |
2 |
Correct |
2 ms |
468 KB |
n = 128 |
3 |
Correct |
2 ms |
432 KB |
n = 128 |
4 |
Correct |
2 ms |
468 KB |
n = 128 |
5 |
Correct |
2 ms |
468 KB |
n = 128 |
6 |
Correct |
2 ms |
424 KB |
n = 128 |
7 |
Correct |
2 ms |
432 KB |
n = 128 |
8 |
Correct |
2 ms |
424 KB |
n = 128 |
9 |
Correct |
2 ms |
468 KB |
n = 128 |
10 |
Correct |
2 ms |
428 KB |
n = 128 |
11 |
Correct |
2 ms |
468 KB |
n = 128 |
12 |
Correct |
2 ms |
428 KB |
n = 128 |
13 |
Correct |
2 ms |
468 KB |
n = 128 |
14 |
Correct |
2 ms |
424 KB |
n = 128 |
15 |
Correct |
2 ms |
468 KB |
n = 128 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
n = 128 |
2 |
Correct |
2 ms |
468 KB |
n = 128 |
3 |
Correct |
1 ms |
480 KB |
n = 128 |
4 |
Correct |
2 ms |
468 KB |
n = 128 |
5 |
Correct |
1 ms |
468 KB |
n = 128 |
6 |
Correct |
2 ms |
468 KB |
n = 128 |
7 |
Correct |
2 ms |
468 KB |
n = 128 |
8 |
Correct |
2 ms |
468 KB |
n = 128 |
9 |
Correct |
2 ms |
468 KB |
n = 128 |
10 |
Correct |
1 ms |
468 KB |
n = 128 |
11 |
Correct |
2 ms |
420 KB |
n = 128 |
12 |
Correct |
2 ms |
428 KB |
n = 128 |
13 |
Correct |
2 ms |
468 KB |
n = 128 |
14 |
Correct |
2 ms |
432 KB |
n = 128 |
15 |
Correct |
2 ms |
468 KB |
n = 128 |