Submission #590647

#TimeUsernameProblemLanguageResultExecution timeMemory
590647LucppCounting Mushrooms (IOI20_mushrooms)C++17
91.87 / 100
9 ms460 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; int count_mushrooms(int n) { int ans = 1; vector<int> a{0}, b; for(int j = 1; j < min(3, n); j++){ if(use_machine({0, j})) b.push_back(j); else ans++, a.push_back(j); } int i = 3; for(int j = 0; j < 60 && n-i >= 2; j++){ if(a.size() >= 2){ int x = use_machine({a[0], i, a[1], i+1}); if(x & 2) b.push_back(i); else ans++, a.push_back(i); if(x & 1) b.push_back(i+1); else ans++, a.push_back(i+1); } else{ int x = use_machine({b[0], i, b[1], i+1}); if(x & 2) ans++, a.push_back(i); else b.push_back(i); if(x & 1) ans++, a.push_back(i+1); else b.push_back(i+1); } i += 2; } while(i < n){ if(a.size() > b.size()){ int s = min((int)a.size(), n-i); vector<int> m; int k = 0; for(int j = i; j < i+s; j++){ m.push_back(a[k++]); m.push_back(j); } int x = use_machine(m); ans += s-(x+1)/2; if(x%2 == 0) a.push_back(i+s-1); else b.push_back(i+s-1); i += s; } else{ int s = min((int)b.size(), n-i); vector<int> m; int k = 0; for(int j = i; j < i+s; j++){ m.push_back(b[k++]); m.push_back(j); } int x = use_machine(m); ans += (x+1)/2; if(x%2 == 0) b.push_back(i+s-1); else a.push_back(i+s-1); i += s; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...