#include "messy.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
void prepare(int n, vector<int> cand, int lvl) {
if(lvl < 0) return;
string s;
For(i, 1, n) s.push_back('1');
for(auto &i:cand) s[i] = '0';
vector<int> c1, c0;
for(auto &i:cand) {
if(i & (1 << lvl)) {
s[i] = '1';
add_element(s);
s[i] = '0';
c1.eb(i);
} else {
c0.eb(i);
}
}
prepare(n, c0, lvl - 1);
prepare(n, c1, lvl - 1);
}
void solve(int n, vector<int> cand, int lvl, int mask, vector<int> &ans) {
if(lvl < 0) {
// for(auto &i:cand) cerr << i << " ";
// cerr << "?????\n";
ans[cand[0]] = mask;
return;
}
string s;
For(i, 1, n) s.push_back('1');
for(auto &i:cand) s[i] = '0';
vector<int> c1, c0;
for(auto &i:cand) {
s[i] = '1';
if(check_element(s)) c1.eb(i);
else c0.eb(i);
s[i] = '0';
}
solve(n, c0, lvl - 1, mask, ans);
solve(n, c1, lvl - 1, mask | (1 << lvl), ans);
}
vector<int32_t> restore_permutation(int32_t n, int32_t w, int32_t r) {
int lg = __lg(n);
vector<int> v(n);
For(i, 0, n - 1) v[i] = i;
prepare(n, v, lg - 1);
compile_set();
vector<int> ans(n);
solve(n, v, lg - 1, 0, ans);
return vector<int32_t>(all(ans));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
n = 8 |
2 |
Correct |
1 ms |
212 KB |
n = 8 |
3 |
Correct |
1 ms |
300 KB |
n = 8 |
4 |
Correct |
1 ms |
212 KB |
n = 8 |
5 |
Correct |
1 ms |
212 KB |
n = 8 |
6 |
Correct |
1 ms |
212 KB |
n = 8 |
7 |
Correct |
1 ms |
296 KB |
n = 8 |
8 |
Correct |
1 ms |
300 KB |
n = 8 |
9 |
Correct |
1 ms |
296 KB |
n = 8 |
10 |
Correct |
1 ms |
304 KB |
n = 8 |
11 |
Correct |
1 ms |
212 KB |
n = 8 |
12 |
Correct |
1 ms |
300 KB |
n = 8 |
13 |
Correct |
1 ms |
300 KB |
n = 8 |
14 |
Correct |
1 ms |
300 KB |
n = 8 |
15 |
Correct |
1 ms |
304 KB |
n = 8 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 32 |
2 |
Correct |
1 ms |
296 KB |
n = 32 |
3 |
Correct |
1 ms |
300 KB |
n = 32 |
4 |
Correct |
1 ms |
300 KB |
n = 32 |
5 |
Correct |
1 ms |
300 KB |
n = 32 |
6 |
Correct |
1 ms |
212 KB |
n = 32 |
7 |
Correct |
1 ms |
296 KB |
n = 32 |
8 |
Correct |
1 ms |
212 KB |
n = 32 |
9 |
Correct |
1 ms |
212 KB |
n = 32 |
10 |
Correct |
1 ms |
256 KB |
n = 32 |
11 |
Correct |
1 ms |
212 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 |
244 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 |
212 KB |
n = 32 |
6 |
Correct |
1 ms |
256 KB |
n = 32 |
7 |
Correct |
1 ms |
212 KB |
n = 32 |
8 |
Correct |
1 ms |
212 KB |
n = 32 |
9 |
Correct |
1 ms |
212 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 |
296 KB |
n = 32 |
15 |
Correct |
1 ms |
212 KB |
n = 32 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
512 KB |
n = 128 |
2 |
Correct |
1 ms |
468 KB |
n = 128 |
3 |
Correct |
1 ms |
468 KB |
n = 128 |
4 |
Correct |
1 ms |
468 KB |
n = 128 |
5 |
Correct |
1 ms |
468 KB |
n = 128 |
6 |
Correct |
1 ms |
468 KB |
n = 128 |
7 |
Correct |
2 ms |
428 KB |
n = 128 |
8 |
Correct |
1 ms |
468 KB |
n = 128 |
9 |
Correct |
2 ms |
468 KB |
n = 128 |
10 |
Correct |
2 ms |
424 KB |
n = 128 |
11 |
Correct |
2 ms |
468 KB |
n = 128 |
12 |
Correct |
2 ms |
468 KB |
n = 128 |
13 |
Correct |
1 ms |
468 KB |
n = 128 |
14 |
Correct |
2 ms |
468 KB |
n = 128 |
15 |
Correct |
2 ms |
468 KB |
n = 128 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
n = 128 |
2 |
Correct |
2 ms |
468 KB |
n = 128 |
3 |
Correct |
2 ms |
424 KB |
n = 128 |
4 |
Correct |
1 ms |
500 KB |
n = 128 |
5 |
Correct |
1 ms |
468 KB |
n = 128 |
6 |
Correct |
1 ms |
480 KB |
n = 128 |
7 |
Correct |
1 ms |
412 KB |
n = 128 |
8 |
Correct |
1 ms |
468 KB |
n = 128 |
9 |
Correct |
1 ms |
428 KB |
n = 128 |
10 |
Correct |
1 ms |
468 KB |
n = 128 |
11 |
Correct |
1 ms |
468 KB |
n = 128 |
12 |
Correct |
1 ms |
468 KB |
n = 128 |
13 |
Correct |
1 ms |
468 KB |
n = 128 |
14 |
Correct |
1 ms |
468 KB |
n = 128 |
15 |
Correct |
1 ms |
428 KB |
n = 128 |