이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int, int>, bool> mp;
bool query(int i, int j) {
if (mp.count({i, j})) {
return mp[{i, j}];
}
mp[{i, j}] = Query(i, j);
mp[{j, i}] = !mp[{i, j}];
return mp[{i, j}];
}
vector<int> my_sort(vector<int> nw) {
map<pair<int, int>, int> vl;
map<int, int> cnt;
for (int i = 0; i < (int)nw.size(); ++i) {
for (int j = i + 1; j < (int)nw.size(); ++j) {
if (query(nw[i], nw[j])) {
vl[{nw[i], nw[j]}] = 1;
cnt[nw[i]]++;
} else {
vl[{nw[j], nw[i]}] = 1;
cnt[nw[j]]++;
}
}
}
int start;
for (int i = 0; i < (int)nw.size(); ++i) {
if (cnt[nw[i]] == 1) {
bool check = true;
for (int j = 0; j < (int)nw.size(); ++j) {
if (vl[{nw[i], nw[j]}] && cnt[nw[j]] != 1) {
check = false;
break;
}
}
if (check) {
start = nw[i];
break;
}
}
}
vector<int> ans = {start};
set<int> used = {start};
while (ans.size() < nw.size()) {
for (int i = 0; i < (int)nw.size(); ++i) {
if (!used.count(nw[i]) && vl[{ans.back(), nw[i]}]) {
ans.push_back(nw[i]);
used.insert(nw[i]);
break;
}
}
}
return ans;
}
vector<int> Solve(int n) {
vector<int> ord = {0};
for (int i = 1; i < n; ++i) {
int l = -1, r = ord.size();
while (l < r - 1) {
int m = (l + r) / 2;
if (query(i, ord[m])) {
l = m;
} else {
r = m;
}
}
vector<int> ord_nw;
for (int j = 0; j <= l; ++j) {
ord_nw.push_back(ord[j]);
}
ord_nw.push_back(i);
for (int j = r; j < (int)ord.size(); ++j) {
ord_nw.push_back(ord[j]);
}
ord = ord_nw;
}
// for (int i = 0; i < n; ++i) {
// cout << ord[i] << ' ';
// }
// cout << endl;
int pos = 0;
vector<int> poses;
while (pos < n - 2) {
int r = pos + 2;
if (query(ord[pos], ord[r])) {
while (r + 1 < n && query(ord[pos], ord[r + 1])) {
r++;
}
if (r == pos + 2) {
poses.push_back(pos);
} else {
if (query(ord[pos + 1], ord[r])) {
reverse(ord.begin() + pos, ord.begin() + r + 1);
} else {
reverse(ord.begin() + pos, ord.begin() + r);
}
}
} else {
while (r + 1 < n && query(ord[r + 1], ord[pos])) {
r++;
}
if (r > pos + 2) {
if (query(ord[r], ord[pos + 1])) {
reverse(ord.begin() + pos, ord.begin() + pos + 2);
reverse(ord.begin() + pos + 2, ord.begin() + r + 2);
r++;
} else {
reverse(ord.begin() + pos + 1, ord.begin() + r + 2);
r++;
}
} else {
vector<int> vals = {ord[pos], ord[pos + 1], ord[pos + 2], ord[pos + 3]};
vals = my_sort(vals);
ord[pos] = vals[0];
ord[pos + 1] = vals[1];
ord[pos + 2] = vals[2];
ord[pos + 3] = vals[3];
r++;
}
}
pos = r + 1;
}
if (pos == n - 2) {
swap(ord[n - 2], ord[n - 1]);
}
for (int i = 0; i < (int)poses.size(); ++i) {
if (poses[i] == -1) {
continue;
}
if (poses[i] != 0) {
vector<int> vals = {ord[poses[i] - 1], ord[poses[i]], ord[poses[i] + 1], ord[poses[i] + 2]};
vals = my_sort(vals);
ord[poses[i]] = vals[1];
ord[poses[i] + 1] = vals[2];
ord[poses[i] + 2] = vals[3];
} else if (i + 1 == (int)poses.size() || poses[i] + 3 != poses[i + 1]) {
vector<int> vals = {ord[poses[i]], ord[poses[i] + 1], ord[poses[i] + 2], ord[poses[i] + 3]};
vals = my_sort(vals);
ord[poses[i]] = vals[0];
ord[poses[i] + 1] = vals[1];
ord[poses[i] + 2] = vals[2];
} else {
vector<int> vals = {ord[poses[i]], ord[poses[i] + 1], ord[poses[i] + 2], ord[poses[i] + 3], ord[poses[i] + 4], ord[poses[i] + 5]};
vals = my_sort(vals);
ord[poses[i]] = vals[0];
ord[poses[i] + 1] = vals[1];
ord[poses[i] + 2] = vals[2];
ord[poses[i] + 3] = vals[3];
ord[poses[i] + 4] = vals[4];
ord[poses[i] + 5] = vals[5];
poses[i + 1] = -1;
}
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[ord[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... |