Submission #831002

#TimeUsernameProblemLanguageResultExecution timeMemory
831002pavementCounting Mushrooms (IOI20_mushrooms)C++17
88.98 / 100
7 ms412 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; #define pb push_back const int k = 77; int count_mushrooms(int n) { vector<int> m(n); if (n <= 2 * k - 1) { for (int i = 1; i < n; i++) { m[i] = use_machine({0, i}); } return count(m.begin(), m.end(), 0); } m[1] = use_machine({0, 1}); m[2] = use_machine({0, 2}); vector<int> sm; if (!m[1]) { sm = {0, 1}; } else if (!m[2]) { sm = {0, 2}; } else { sm = {1, 2}; } for (int i = 3; i + 1 < 2 * k - 1; i += 2) { int x = use_machine({sm[0], i, sm[1], i + 1}); if (x == 0) { m[i] = m[i + 1] = m[sm[0]]; } else if (x == 1) { m[i] = m[sm[0]]; m[i + 1] = !m[sm[0]]; } else if (x == 2) { m[i] = !m[sm[0]]; m[i + 1] = m[sm[0]]; } else if (x == 3) { m[i] = m[i + 1] = !m[sm[0]]; } } int dom; if (count(m.begin(), m.begin() + 2 * k - 1, 0) > count(m.begin(), m.begin() + 2 * k - 1, 1)) dom = 0; else dom = 1; sm.clear(); for (int i = 0; i < 2 * k - 1; i++) { if (m[i] == dom) { sm.pb(i); } } int ans = count(m.begin(), m.begin() + 2 * k - 1, 0); for (int i = 2 * k - 1; i < n; ) { vector<int> cur; for (int j = i; j < min(n, i + (int)sm.size()); j++) { cur.pb(j); cur.pb(sm[j - i]); } int tmp = use_machine(cur); if (tmp % 2 == 0) { sm.pb(i); } int diff = (tmp + 1) / 2; if (dom == 0) { ans += (int)cur.size() / 2 - diff; } else { ans += diff; } i += (int)cur.size() / 2; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...