Submission #654446

#TimeUsernameProblemLanguageResultExecution timeMemory
654446StickfishMonster Game (JOI21_monster)C++17
10 / 100
224 ms4200 KiB
#include "monster.h" #include <algorithm> #include <random> using namespace std; mt19937 rng(177013); namespace { bool example_variable; } // namespace const int MAXN = 1001; int hoh[MAXN][MAXN]; bool qr(int i, int j) { if (hoh[i][j] != -1) return hoh[i][j]; bool ans = Query(i, j); hoh[i][j] = ans; hoh[j][i] = !ans; return ans; } int trim(vector<int> a, bool type) { int m = a.size(); int cnt = 0; vector<int> a0; for (int i = 1; i < m; ++i) { if (qr(a[0], a[i]) ^ type) a0.push_back(a[i]); } if (a0.empty()) return a[0]; return trim(a0, type); } int fact(int n) { int ans = 1; for (int k = 2; k <= n; ++k) ans *= k; return ans; } void solve_bad(vector<int> a, vector<int>& ans, int l) { int m = a.size(); for (int i = 0; i < m; ++i) { ans[a[i]] = l; for (int j = 0; j < m; ++j) { if (i == j) continue; ans[a[i]] += qr(a[i], a[j]); } } if (m < 4) { sort(a.begin(), a.end()); int pmt = fact(m); for (int t = 0; t < pmt; ++t) { bool isok = true; for (int i = 0; i + 1 < m && isok; ++i) { isok &= qr(a[i], a[i + 1]); for (int j = i + 2; j < m && isok; ++j) isok &= qr(a[j], a[i]); } if (isok) { for (int i = 0; i < m; ++i) ans[a[i]] = l + i; break; } next_permutation(a.begin(), a.end()); } } else { for (int i = 0; i < m; ++i) { for (int j = i + 1; j < m; ++j) { if (ans[a[i]] == ans[a[j]]) { if (qr(a[i], a[j])) swap(a[i], a[j]); if (ans[a[i]] == l + 1) --ans[a[j]]; else ++ans[a[i]]; } } } } } void solve_part(vector<int> a, vector<int>& ans, int l) { solve_bad(a, ans, l); return; if (a.empty()) return; if (a.size() == 1) { ans[a[0]] = l; } int cnt = 0; int m = a.size(); for (int i = 1; i < m; ++i) { cnt += qr(a[0], a[i]); } if (4 < cnt && cnt < m - 5) { ans[a[0]] = l + cnt; vector<int> low; vector<int> high; for (int i = 1; i < m; ++i) { if (qr(a[0], a[i])) low.push_back(a[i]); else high.push_back(a[i]); } int lowhigh = trim(low, 1); int highlow = trim(high, 0); low.erase(find(low.begin(), low.end(), lowhigh)); low.push_back(highlow); high.erase(find(high.begin(), high.end(), highlow)); high.push_back(lowhigh); solve_part(low, ans, l); solve_part(high, ans, l + cnt + 1); } else { solve_bad(a, ans, l); } } vector<int> Solve(int n) { for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) hoh[i][j] = -1; vector<int> vs(n); for (int i = 0; i < n; ++i) vs[i] = i; shuffle(vs.begin(), vs.end(), rng); vector<int> ans(n); solve_part(vs, ans, 0); return ans; }

Compilation message (stderr)

monster.cpp: In function 'int trim(std::vector<int>, bool)':
monster.cpp:28:9: warning: unused variable 'cnt' [-Wunused-variable]
   28 |     int cnt = 0;
      |         ^~~
monster.cpp: At global scope:
monster.cpp:10:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
   10 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...