Submission #1033323

#TimeUsernameProblemLanguageResultExecution timeMemory
1033323happy_nodeCounting Mushrooms (IOI20_mushrooms)C++17
76.09 / 100
8 ms852 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; const int B=100; int count_mushrooms(int N) { vector<int> posA, posB; posA.push_back(0); for(int i=1;i<min(N,B);i++) { if(use_machine({0,i})==0) posA.push_back(i); else posB.push_back(i); } int ans=posA.size(); for(int i=B;i<N;i++) { if(posA.size()>posB.size()) { int s=posA.size(); vector<int> qry; for(int j=i;j<min(N,i+s);j++) { qry.push_back(posA[j-i]); qry.push_back(j); } int w=use_machine(qry); if(w&1) posB.push_back(qry.back()); else posA.push_back(qry.back()); w=(w+1)/2; ans+=(qry.size()/2-w); i+=s-1; } else { int s=posB.size(); vector<int> qry; for(int j=i;j<min(N,i+s);j++) { qry.push_back(posB[j-i]); qry.push_back(j); } int w=use_machine(qry); if(w&1) posA.push_back(qry.back()); else posB.push_back(qry.back()); w=(w+1)/2; ans+=w; i+=s-1; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...