이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(57);
int get_mx(vector<int> nw) {
int ans = nw[0];
for (int i = 1; i < (int)nw.size(); ++i) {
if (Query(nw[i], ans)) {
ans = nw[i];
}
}
return ans;
}
int get_mn(vector<int> nw) {
int ans = nw[0];
for (int i = 1; i < (int)nw.size(); ++i) {
if (Query(ans, nw[i])) {
ans = nw[i];
}
}
return ans;
}
vector<int> my_sort(vector<int> nw) {
if (nw.size() <= 1) {
return nw;
}
if (nw.size() <= 20) {
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> ord_check = nw;
shuffle(ord_check.begin(), ord_check.end(), rnd);
for (auto val_md : ord_check) {
vector<int> l, r;
for (int i = 0; i < (int)nw.size(); ++i) {
if (nw[i] == val_md) {
continue;
}
if (Query(val_md, nw[i])) {
l.push_back(nw[i]);
} else {
r.push_back(nw[i]);
}
}
if (l.size() <= 4 || r.size() <= 4) {
continue;
}
int l_mx = get_mx(l), r_mn = get_mn(r);
vector<int> ll, rr;
for (auto vl : l) {
if (vl != l_mx) {
ll.push_back(vl);
}
}
for (auto vl : r) {
if (vl != r_mn) {
rr.push_back(vl);
}
}
ll = my_sort(ll);
rr = my_sort(rr);
vector<int> ans = ll;
ans.push_back(r_mn);
ans.push_back(val_md);
ans.push_back(l_mx);
for (auto vl : rr) {
ans.push_back(vl);
}
return ans;
}
}
vector<int> Solve(int n) {
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
ord = my_sort(ord);
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[ord[i]] = i;
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
monster.cpp: In function 'std::vector<int> my_sort(std::vector<int>)':
monster.cpp:76:29: warning: control reaches end of non-void function [-Wreturn-type]
76 | vector<int> ord_check = nw;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |