제출 #951691

#제출 시각아이디문제언어결과실행 시간메모리
951691arbuzickMonster Game (JOI21_monster)C++17
25 / 100
118 ms1660 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...