Submission #824018

#TimeUsernameProblemLanguageResultExecution timeMemory
824018drdilyorCounting Mushrooms (IOI20_mushrooms)C++17
0 / 100
0 ms208 KiB
#include<bits/stdc++.h> #include "mushrooms.h" using namespace std; using ll = long long; int count_mushrooms(int n) { const int B = 3; // sqrt(4n) vector<int> t(n); t[1] = use_machine({0, 1}); if (n == 2) return 2 - t[1] - t[0]; t[2] = use_machine({0, 2}); bool inv = false; int cmp1, cmp2; if (t[1] && t[2]) { cmp1 = 1; cmp2 = 2; inv = true; t[0] ^= 1; t[1] ^= 1; t[2] ^= 1; } else { cmp1 = 0; if (!t[1]) cmp2 = 1; else cmp2 = 2; } for (int i = 3; i < n-1 && i < B; i += 2) { int res = use_machine({cmp1, i, cmp2, i+1}); t[i] = res / 2; t[i+1] = res % 2; } if (inv) for (int& i : t) i ^= 1; if (n < B && n % 2 == 0) t[n-1] = use_machine({0, n-1}); int ans = n - accumulate(t.begin(), t.begin() + B, 0); if (n <= B) return ans; vector<int> As, Bs; for (int i = 0; i < B; i++) { if (t[i] == 0) As.push_back(i); else Bs.push_back(i); } vector<int> grp = As.size() > Bs.size() ? As : Bs; for (int j = B; j < n; j += B / 2) { vector<int> cur{grp.front()}; int all_cnt = 0; for (int k = j; k < n && k < j + B / 2; k++) { cur.push_back(k); cur.push_back(grp[k - j + 1]); all_cnt++; } int cnt = use_machine(cur); assert(cnt % 2 == 0); cnt /= 2; if (grp == Bs) { ans += cnt; } else { ans += all_cnt - cnt; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...