#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#ifdef tabr
function<void(string)> add_element;
function<void()> compile_set;
function<bool(string)> check_element;
#else
#include "messy.h"
#endif
vector<int> restore_permutation(int n, int, int) {
int k = __builtin_ctz(n);
for (int t = k - 1; t >= 0; t--) {
for (int i = 0; i < n; i++) {
if (i & (1 << t)) {
string s(n, '0');
s[i] = '1';
for (int j = 0; j < n; j++) {
if ((i ^ j) >> (t + 1)) {
s[j] = '1';
}
}
add_element(s);
debug(s);
}
}
}
compile_set();
vector<int> p(n);
function<void(vector<int>)> dfs = [&](vector<int> a) {
// debug(a.size());
if (a.size() == 1) {
return;
}
int sz = (int) a.size();
string s(n, '1');
for (int i : a) {
s[i] = '0';
}
vector<int> b, c;
for (int i : a) {
s[i] = '1';
if (check_element(s)) {
p[i] |= sz >> 1;
b.emplace_back(i);
} else {
c.emplace_back(i);
}
s[i] = '0';
}
dfs(b);
dfs(c);
};
vector<int> a(n);
iota(a.begin(), a.end(), 0);
dfs(a);
return p;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), rng);
vector<string> t;
int cnt0 = 0;
int cnt1 = 0;
add_element = [&](string x) {
cnt0++;
t.emplace_back(x);
};
compile_set = [&]() {
for (string& x : t) {
string y = x;
for (int i = 0; i < n; i++) {
x[p[i]] = y[i];
}
}
sort(t.begin(), t.end());
};
check_element = [&](string x) {
cnt1++;
return binary_search(t.begin(), t.end(), x);
};
auto q = restore_permutation(n, 0, 0);
debug(p);
debug(q);
for (int i = 0; i < n; i++) {
assert(q[p[i]] == i);
}
debug(cnt0, cnt1);
return 0;
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
n = 8 |
2 |
Correct |
1 ms |
204 KB |
n = 8 |
3 |
Correct |
0 ms |
204 KB |
n = 8 |
4 |
Correct |
1 ms |
204 KB |
n = 8 |
5 |
Correct |
0 ms |
204 KB |
n = 8 |
6 |
Correct |
0 ms |
204 KB |
n = 8 |
7 |
Correct |
0 ms |
204 KB |
n = 8 |
8 |
Correct |
0 ms |
204 KB |
n = 8 |
9 |
Correct |
0 ms |
204 KB |
n = 8 |
10 |
Correct |
0 ms |
204 KB |
n = 8 |
11 |
Correct |
0 ms |
204 KB |
n = 8 |
12 |
Correct |
1 ms |
204 KB |
n = 8 |
13 |
Correct |
0 ms |
204 KB |
n = 8 |
14 |
Correct |
0 ms |
204 KB |
n = 8 |
15 |
Correct |
1 ms |
204 KB |
n = 8 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
n = 32 |
2 |
Correct |
1 ms |
204 KB |
n = 32 |
3 |
Correct |
0 ms |
204 KB |
n = 32 |
4 |
Correct |
1 ms |
204 KB |
n = 32 |
5 |
Correct |
1 ms |
204 KB |
n = 32 |
6 |
Correct |
1 ms |
204 KB |
n = 32 |
7 |
Correct |
0 ms |
204 KB |
n = 32 |
8 |
Correct |
0 ms |
204 KB |
n = 32 |
9 |
Correct |
1 ms |
204 KB |
n = 32 |
10 |
Correct |
1 ms |
204 KB |
n = 32 |
11 |
Correct |
1 ms |
204 KB |
n = 32 |
12 |
Correct |
0 ms |
204 KB |
n = 32 |
13 |
Correct |
1 ms |
204 KB |
n = 32 |
14 |
Correct |
0 ms |
204 KB |
n = 32 |
15 |
Correct |
1 ms |
204 KB |
n = 32 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
n = 32 |
2 |
Correct |
1 ms |
204 KB |
n = 32 |
3 |
Correct |
1 ms |
204 KB |
n = 32 |
4 |
Correct |
0 ms |
204 KB |
n = 32 |
5 |
Correct |
1 ms |
204 KB |
n = 32 |
6 |
Correct |
0 ms |
204 KB |
n = 32 |
7 |
Correct |
1 ms |
204 KB |
n = 32 |
8 |
Correct |
1 ms |
204 KB |
n = 32 |
9 |
Correct |
1 ms |
204 KB |
n = 32 |
10 |
Correct |
1 ms |
204 KB |
n = 32 |
11 |
Correct |
0 ms |
204 KB |
n = 32 |
12 |
Correct |
0 ms |
204 KB |
n = 32 |
13 |
Correct |
1 ms |
204 KB |
n = 32 |
14 |
Correct |
0 ms |
204 KB |
n = 32 |
15 |
Correct |
1 ms |
204 KB |
n = 32 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
n = 128 |
2 |
Correct |
1 ms |
460 KB |
n = 128 |
3 |
Correct |
1 ms |
460 KB |
n = 128 |
4 |
Correct |
2 ms |
460 KB |
n = 128 |
5 |
Correct |
2 ms |
460 KB |
n = 128 |
6 |
Correct |
2 ms |
460 KB |
n = 128 |
7 |
Correct |
2 ms |
460 KB |
n = 128 |
8 |
Correct |
1 ms |
460 KB |
n = 128 |
9 |
Correct |
1 ms |
460 KB |
n = 128 |
10 |
Correct |
1 ms |
460 KB |
n = 128 |
11 |
Correct |
1 ms |
460 KB |
n = 128 |
12 |
Correct |
1 ms |
460 KB |
n = 128 |
13 |
Correct |
1 ms |
460 KB |
n = 128 |
14 |
Correct |
1 ms |
460 KB |
n = 128 |
15 |
Correct |
1 ms |
460 KB |
n = 128 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
460 KB |
n = 128 |
2 |
Correct |
1 ms |
460 KB |
n = 128 |
3 |
Correct |
1 ms |
460 KB |
n = 128 |
4 |
Correct |
2 ms |
460 KB |
n = 128 |
5 |
Correct |
2 ms |
460 KB |
n = 128 |
6 |
Correct |
1 ms |
460 KB |
n = 128 |
7 |
Correct |
2 ms |
460 KB |
n = 128 |
8 |
Correct |
1 ms |
460 KB |
n = 128 |
9 |
Correct |
1 ms |
460 KB |
n = 128 |
10 |
Correct |
1 ms |
460 KB |
n = 128 |
11 |
Correct |
1 ms |
460 KB |
n = 128 |
12 |
Correct |
1 ms |
460 KB |
n = 128 |
13 |
Correct |
2 ms |
460 KB |
n = 128 |
14 |
Correct |
1 ms |
460 KB |
n = 128 |
15 |
Correct |
1 ms |
460 KB |
n = 128 |