Submission #307410

#TimeUsernameProblemLanguageResultExecution timeMemory
307410arthur_nascimentoCounting Mushrooms (IOI20_mushrooms)C++14
92.62 / 100
9 ms512 KiB
#include "mushrooms.h" #define pb push_back using namespace std; const int C = 159; int count_mushrooms(int n) { vector<int> A,B; A.pb(0); for(int i=1;i<min(3,n);i++){ vector<int> v; v.pb(0); v.pb(i); int x = use_machine(v); if(x) B.pb(i); else A.pb(i); } int ua = 1; if(B.size() > A.size()) ua = 0; int nx = 3; for(int i=3;i<min(C,n-2);i+=2){ if(ua){ vector<int> v = {A[0],i,A[1],i+1}; int x = use_machine(v); if(x >= 2) B.pb(i); else A.pb(i); if(x%2 == 1) B.pb(i+1); else A.pb(i+1); } else { vector<int> v = {B[0],i,B[1],i+1}; int x = use_machine(v); if(x >= 2) A.pb(i); else B.pb(i); if(x%2 == 1) A.pb(i+1); else B.pb(i+1); } nx = i+2; } int ans = A.size(); int eff = 0; for(int i=nx;i<n;){ int t = max(A.size(), B.size()); int use = 0; if(B.size() > A.size()) use = 1; vector<int> vec = A; if(use) vec = B; vector<int> v; int spec = -1; eff = 0; for(int j=0;j<t;j++){ v.pb(vec[j]); if(j < t-1 && i+j < n) v.pb(i+j), eff++; if(j == t-1 && i+j < n){ v.pb(i+j); spec = i+j; } } int x = use_machine(v); //printf("ff %d\n",eff); if(use) ans += x/2; else ans += eff - (x/2); if(spec+1){ if(x%2 != use){ B.pb(spec); } else { A.pb(spec); ans++; } } i += t-1; if(spec+1) i++; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...