제출 #894076

#제출 시각아이디문제언어결과실행 시간메모리
894076MilosMilutinovicMonster Game (JOI21_monster)C++17
96 / 100
55 ms1196 KiB
#include "monster.h" #include <bits/stdc++.h> using namespace std; namespace { bool example_variable; } // namespace vector<int> Solve(int n) { vector<int> order(n); iota(order.begin(), order.end(), 0); vector<int> tmp(n); function<void(int, int)> MergeSort = [&](int l, int r) { if (l == r) { return; } int mid = l + r >> 1; MergeSort(l, mid); MergeSort(mid + 1, r); for (int i = l; i <= r; i++) { tmp[i] = order[i]; } int pl = l, pr = mid + 1; int ptr = l; while (pl <= mid || pr <= r) { if (pl > mid) { order[ptr++] = tmp[pr++]; } else if (pr > r) { order[ptr++] = tmp[pl++]; } else { order[ptr++] = (Query(tmp[pl], tmp[pr]) ? tmp[pl++] : tmp[pr++]); } } }; MergeSort(0, n - 1); int pos = -1; auto Check = [&]() { if (Query(order[0], order[2])) { return false; } if (!Query(order[0], order[1])) { return false; } if (!Query(order[1], order[2])) { return false; } return true; }; if (n <= 10) { vector<int> bad; for (int i = 1; i < n; i++) { if (!Query(order[0], order[i])) { bad.push_back(i); } } if ((int) bad.size() > 1) { pos = bad.rbegin()[1]; } else { bool ok = true; for (int i = 2; i < n; i++) { if (!Query(order[1], order[i])) { ok = false; break; } } if (ok) { pos = 1; } else { pos = 0; } } } else { if (Check()) { if (!Query(order[0], order[3]) && !Query(order[1], order[3])) { vector<int> bad; for (int i = 1; i < n; i++) { if (!Query(order[0], order[i])) { bad.push_back(i); } } pos = bad.rbegin()[1]; } else { int smx = -1; vector<int> cnt(3); auto Update = [&](int x) { for (int i = 0; i < 3; i++) { cnt[i] += !Query(order[i], x); } }; if (!Query(order[3], order[5]) && Query(order[3], order[4]) && Query(order[4], order[5])) { if (!Query(order[3], order[6]) && !Query(order[4], order[6])) { vector<int> bad(order[6]); for (int i = 7; i < n; i++) { if (!Query(order[3], order[i])) { bad.push_back(order[i]); } } if ((int) bad.size() > 1) { bad.pop_back(); } Update(bad.back()); } else { for (int i = 3; i < 6; i++) { Update(order[i]); } } } else { bool ok = true; for (int i = 5; i < n; i++) { if (!Query(order[4], order[i])) { ok = false; break; } } if (ok) { Update(order[4]); } else { Update(order[3]); } } for (int i = 0; i < 3; i++) { if (cnt[i] > 0) { pos = (i - 1 + 3) % 3; } } } } else { bool ok = true; for (int i = 2; i < n; i++) { if (!Query(order[1], order[i])) { ok = false; break; } } if (ok) { pos = 1; } else { pos = 0; } } } vector<int> res; function<void(int, int)> Solve = [&](int l, int r) { for (int i = r; i >= l; i--) { res.push_back(order[i]); } if (r == n - 1) { return; } for (int i = r + 1; i < n; i++) { if (!Query(order[l], order[i])) { Solve(r + 1, i); break; } } }; Solve(0, pos); reverse(res.begin(), res.end()); vector<int> ret(n); for (int i = 0; i < n; i++) { ret[res[i]] = i; } return ret; }

컴파일 시 표준 에러 (stderr) 메시지

monster.cpp: In lambda function:
monster.cpp:20:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     int mid = l + r >> 1;
      |               ~~^~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:86:13: warning: unused variable 'smx' [-Wunused-variable]
   86 |         int smx = -1;
      |             ^~~
monster.cpp: At global scope:
monster.cpp:8:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
    8 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...