이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "messy.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
vector<int> restore_permutation(int n, int w, int r) {
string s, t;
for (int i = 0; i < n; i++) {
s.push_back('1');
t.push_back('0');
}
for (int i = 1; i < n; i *= 2) {
s[i] = '0';
// cout << "> " << s << '\n';
add_element(s);
if (i % 2 == 0) s[i / 2] = '1';
}
int lg = __lg(n);
for (int i = 0; i < n; i++) {
if ((i & -i) == i) continue;
for (int j = 0; j < lg; j++) {
if ((i >> j) & 1) {
t[i] = '1';
t[1 << j] = '1';
add_element(t);
t[1 << j] = '0';
t[i] = '0';
}
}
}
compile_set();
vector<int> p(n, -1);
for (int i = 0; i < n; i++) s[i] = '1', t[i] = '0';
for (int j = 0; j < lg; j++) {
for (int k = 0; k < n; k++) {
if (s[k] == '0') continue;
s[k] = '0';
if (check_element(s)) {
// cout << s << '\n';
p[1 << j] = k;
break;
}
s[k] = '1';
}
if (j - 1 >= 0) {
s[p[1 << (j - 1)]] = '1';
}
}
// for (auto i : p) {
// cout << i << ' ';
// }
// cout << endl;
set<int> gud[lg];
for (int j = 0; j < lg; j++) {
t[p[1 << j]] = '1';
for (int k = 0; k < n; k++) {
if (t[k] == '1') continue;
t[k] = '1';
if (check_element(t)) {
gud[j].insert(k);
}
t[k] = '0';
}
t[p[1 << j]] = '0';
}
// for (int j = 0; j < lg; j++) {
// for (auto i : gud[j]) {
// cout << i << ' ';
// }
// cout << '\n';
// }
vector<int> order;
for (int i = 0; i < n; i++) {
if ((i & -i) == i && i) continue;
order.push_back(i);
}
sort(order.begin(), order.end(), [&] (int x, int y) {return __builtin_popcount(x) > __builtin_popcount(y);});
set<int> rem;
for (int i = 0; i < n; i++) {
rem.insert(i);
}
for (int i = 1; i < n; i *= 2) {
rem.erase(p[i]);
}
for (auto i : order) {
set<int> cur = rem;
for (int j = 0; j < lg; j++) {
if ((i >> j) & 1) {
set<int> cur2;
for (auto k : cur) {
if (gud[j].find(k) != gud[j].end()) {
cur2.insert(k);
}
}
cur = cur2;
}
}
int pos = *cur.begin();
// cout << i << ' ' << pos << '\n';
p[i] = pos;
rem.erase(pos);
}
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[p[i]] = i;
}
return ans;
}
# | 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... |