제출 #1204855

#제출 시각아이디문제언어결과실행 시간메모리
1204855banganCounting Mushrooms (IOI20_mushrooms)C++20
91.13 / 100
3 ms520 KiB
#include "mushrooms.h" using namespace std; const int A = 227; int count_mushrooms(int n) { if (n <= A) { int ans = 1; for (int i = 1; i < n; i++) { vector<int> g = {0, i}; ans += !use_machine(g); } return ans; } vector<int> st(A, 0); st[1] = use_machine({0, 1}); st[2] = use_machine({0, 2}); int p = 0; if (st[1] == st[2] && st[1] == 1) { p = 0; } else if (st[0] == st[1]) { p = 1; } else { p = 2; } for (int i = 3; i < A; i += 2) { int res = 0; if (p) { res = use_machine({0, i, p, i + 1}); if (res == 0) { st[i] = st[i + 1] = 0; } else if (res == 1) { st[i + 1] = 1; } else if (res == 2) { st[i] = 1; } else { st[i] = st[i + 1] = 1; } } else { res = use_machine({1, i, 2, i + 1}); if (res == 0) { st[i] = st[i + 1] = 1; } else if (res == 1) { st[i] = 1; } else if (res == 2) { st[i + 1] = 1; } else { st[i] = st[i + 1] = 0; } } } int cnt = 0, ans = 0; for (int i = 0; i < A; i++) { ans += !st[i]; cnt += st[i]; } vector<int> g[2]; int t = (cnt > A / 2); for (int i = 0; i < A; i++) { if (st[i] == t) { g[0].push_back(i); } else { g[1].push_back(i); } } vector<int> rem; for (int i = A; i < n; i++) { rem.push_back(i); } while (!rem.empty()) { if (g[0].size() < g[1].size()) { t = 1 - t; swap(g[0], g[1]); } vector<int> x; while (!rem.empty() && !g[0].empty()) { x.push_back(rem.back()); x.push_back(g[0].back()); rem.pop_back(); g[0].pop_back(); } int res = use_machine(x); if (res % 2 == 1) { res++; g[1].push_back(x[0]); } else { g[0].push_back(x[0]); } res /= 2; if (t == 1) { ans += res; } else { int sz = (int)x.size(); sz /= 2; ans += sz - res; } while (!x.empty()) { g[0].push_back(x.back()); x.pop_back(); x.pop_back(); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...