// moreflags=grader.cpp
#include <vector>
// 15
// (somehow the wrong solution breaks at the sample solution... and I didn't notice it!?)
#include "messy.h"
#if not LOCAL
#define NDEBUG 1
#endif
#include<cassert>
template<bool write> std::vector<int> process(int n, std::vector<int> a, std::vector<int> pivot){
auto const sizea=(int)a.size();
auto const numBit=__builtin_ctz(sizea);
assert(sizea==(1<<numBit));
if(sizea==1) return a;
auto const half=sizea>>1;
if(write){
std::vector<int> first(a.begin(), a.begin()+half), sec(a.begin()+half, a.end());
for(auto it: first){
std::string tmp(n,'0');
for(auto it: pivot) tmp[it]='1';
tmp[it]='1';
add_element(std::move(tmp));
}
process<true>(n, first, sec);
process<true>(n, sec, first);
return {};
}else{
std::vector<int> first, sec;
for(auto it: a){
std::string tmp(n,'0');
for(auto it: pivot) tmp[it]='1';
tmp[it]='1';
if(check_element(std::move(tmp)))
first.push_back(it);
else
sec.push_back(it);
}
assert((int)first.size()==half);
assert((int)sec.size()==half);
auto result=process<false>(n, first, sec);
auto result2=process<false>(n, sec, first);
result.insert(result.end(),begin(result2), end(result2));
return result;
}
}
std::vector<int> restore_permutation(int n, int w, int r) {
std::vector<int> all(n);
for(int i=0; i<n; ++i) all[i]=i;
process<true>(n, all,{});
compile_set();
auto const result1=process<false>(n, std::move(all),{});
std::vector<int> result(n);
for(int index=0; index<n; ++index)
result[result1[index]]=index;
return result;
}
Compilation message
messy.cpp: In instantiation of 'std::vector<int> process(int, std::vector<int>, std::vector<int>) [with bool write = true]':
messy.cpp:55:25: required from here
messy.cpp:14:13: warning: unused variable 'numBit' [-Wunused-variable]
14 | auto const numBit=__builtin_ctz(sizea);
| ^~~~~~
messy.cpp: In instantiation of 'std::vector<int> process(int, std::vector<int>, std::vector<int>) [with bool write = false]':
messy.cpp:57:56: required from here
messy.cpp:14:13: warning: unused variable 'numBit' [-Wunused-variable]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 8 |
2 |
Correct |
1 ms |
256 KB |
n = 8 |
3 |
Correct |
0 ms |
256 KB |
n = 8 |
4 |
Correct |
0 ms |
256 KB |
n = 8 |
5 |
Correct |
1 ms |
256 KB |
n = 8 |
6 |
Correct |
1 ms |
256 KB |
n = 8 |
7 |
Correct |
1 ms |
256 KB |
n = 8 |
8 |
Correct |
0 ms |
256 KB |
n = 8 |
9 |
Correct |
1 ms |
256 KB |
n = 8 |
10 |
Correct |
1 ms |
256 KB |
n = 8 |
11 |
Correct |
1 ms |
256 KB |
n = 8 |
12 |
Correct |
1 ms |
256 KB |
n = 8 |
13 |
Correct |
1 ms |
256 KB |
n = 8 |
14 |
Correct |
1 ms |
256 KB |
n = 8 |
15 |
Correct |
0 ms |
256 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
n = 32 |
2 |
Correct |
1 ms |
384 KB |
n = 32 |
3 |
Correct |
1 ms |
400 KB |
n = 32 |
4 |
Correct |
1 ms |
384 KB |
n = 32 |
5 |
Correct |
1 ms |
384 KB |
n = 32 |
6 |
Correct |
1 ms |
384 KB |
n = 32 |
7 |
Correct |
1 ms |
384 KB |
n = 32 |
8 |
Correct |
1 ms |
384 KB |
n = 32 |
9 |
Correct |
1 ms |
384 KB |
n = 32 |
10 |
Correct |
1 ms |
384 KB |
n = 32 |
11 |
Correct |
1 ms |
384 KB |
n = 32 |
12 |
Correct |
1 ms |
384 KB |
n = 32 |
13 |
Correct |
1 ms |
416 KB |
n = 32 |
14 |
Correct |
1 ms |
384 KB |
n = 32 |
15 |
Correct |
1 ms |
384 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
n = 32 |
2 |
Correct |
1 ms |
384 KB |
n = 32 |
3 |
Correct |
1 ms |
384 KB |
n = 32 |
4 |
Correct |
1 ms |
384 KB |
n = 32 |
5 |
Correct |
1 ms |
384 KB |
n = 32 |
6 |
Correct |
1 ms |
384 KB |
n = 32 |
7 |
Correct |
1 ms |
384 KB |
n = 32 |
8 |
Correct |
1 ms |
384 KB |
n = 32 |
9 |
Correct |
1 ms |
384 KB |
n = 32 |
10 |
Correct |
1 ms |
384 KB |
n = 32 |
11 |
Correct |
1 ms |
384 KB |
n = 32 |
12 |
Correct |
1 ms |
384 KB |
n = 32 |
13 |
Correct |
1 ms |
384 KB |
n = 32 |
14 |
Correct |
1 ms |
384 KB |
n = 32 |
15 |
Correct |
1 ms |
288 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
512 KB |
n = 128 |
2 |
Correct |
2 ms |
512 KB |
n = 128 |
3 |
Correct |
3 ms |
640 KB |
n = 128 |
4 |
Correct |
2 ms |
512 KB |
n = 128 |
5 |
Correct |
2 ms |
512 KB |
n = 128 |
6 |
Correct |
2 ms |
512 KB |
n = 128 |
7 |
Correct |
2 ms |
512 KB |
n = 128 |
8 |
Correct |
2 ms |
512 KB |
n = 128 |
9 |
Correct |
2 ms |
512 KB |
n = 128 |
10 |
Correct |
2 ms |
512 KB |
n = 128 |
11 |
Correct |
2 ms |
512 KB |
n = 128 |
12 |
Correct |
2 ms |
512 KB |
n = 128 |
13 |
Correct |
2 ms |
512 KB |
n = 128 |
14 |
Correct |
2 ms |
512 KB |
n = 128 |
15 |
Correct |
2 ms |
512 KB |
n = 128 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
512 KB |
n = 128 |
2 |
Correct |
2 ms |
512 KB |
n = 128 |
3 |
Correct |
2 ms |
512 KB |
n = 128 |
4 |
Correct |
2 ms |
512 KB |
n = 128 |
5 |
Correct |
2 ms |
512 KB |
n = 128 |
6 |
Correct |
2 ms |
512 KB |
n = 128 |
7 |
Correct |
2 ms |
512 KB |
n = 128 |
8 |
Correct |
2 ms |
512 KB |
n = 128 |
9 |
Correct |
2 ms |
512 KB |
n = 128 |
10 |
Correct |
2 ms |
512 KB |
n = 128 |
11 |
Correct |
2 ms |
512 KB |
n = 128 |
12 |
Correct |
2 ms |
564 KB |
n = 128 |
13 |
Correct |
2 ms |
512 KB |
n = 128 |
14 |
Correct |
2 ms |
512 KB |
n = 128 |
15 |
Correct |
2 ms |
512 KB |
n = 128 |