제출 #951842

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