이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 i = 0; i < k; i++) {
string s(n, '0');
s[i] = '1';
add_element(s);
}
for (int i = 0; i < k - 1; i++) {
string s(n, '0');
s[i] = s[i + 1] = '1';
add_element(s);
}
for (int i = k; i < n; i++) {
for (int j = 0; j < k; j++) {
if (i & (1 << j)) {
string s(n, '0');
s[i] = s[j] = '1';
add_element(s);
}
}
}
{
string s(n, '1');
s[0] = '0';
add_element(s);
}
compile_set();
vector<int> p(n, -1);
set<int> st;
for (int i = 0; i < n; i++) {
string s(n, '0');
s[i] = '1';
if (check_element(s)) {
st.emplace(i);
}
}
debug(st);
vector<int> q(k);
for (int i : st) {
string s(n, '1');
s[i] = '0';
if (check_element(s)) {
q[0] = i;
st.erase(i);
break;
}
}
for (int i = 1; i < k - 1; i++) {
for (int j : st) {
string s(n, '0');
s[q[i - 1]] = s[j] = '1';
if (check_element(s)) {
q[i] = j;
st.erase(j);
break;
}
}
}
q[k - 1] = *st.begin();
for (int i = 0; i < k; i++) {
p[q[i]] = i;
}
for (int i = 0; i < n; i++) {
if (p[i] != -1) {
continue;
}
p[i] = 0;
for (int j = 0; j < k; j++) {
string s(n, '0');
s[i] = s[q[j]] = '1';
if (check_element(s)) {
p[i] |= 1 << j;
}
}
}
vector<int> res(n);
for (int i = 0; i < n; i++) {
res[p[i]] = i;
}
return res;
}
#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;
add_element = [&](string x) {
debug(x);
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) {
return binary_search(t.begin(), t.end(), x);
};
debug(p);
debug(restore_permutation(n, 0, 0));
return 0;
}
#endif
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |