Submission #1033379

#TimeUsernameProblemLanguageResultExecution timeMemory
1033379happy_nodeCounting Mushrooms (IOI20_mushrooms)C++17
90.40 / 100
6 ms724 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; const int B=50; int count_mushrooms(int N) { vector<int> posA, posB; posA.push_back(0); if(use_machine({0,1})==0) posA.push_back(1); else posB.push_back(1); if(N>2) { if(use_machine({0,2})==0) posA.push_back(2); else posB.push_back(2); } else { return posA.size(); } int lst=2; for(int i=3;i+1<min(N,2*B);i+=2) { if(posA.size()>=2) { vector<int> qry={posA[0],i,posA[1],i+1}; int res=use_machine(qry); if(res==0) { posA.push_back(i); posA.push_back(i+1); } else if(res==1) { posA.push_back(i); posB.push_back(i+1); } else if(res==2) { posB.push_back(i); posA.push_back(i+1); } else { posB.push_back(i); posB.push_back(i+1); } } else { vector<int> qry={posB[0],i,posB[1],i+1}; int res=use_machine(qry); if(res==0) { posB.push_back(i); posB.push_back(i+1); } else if(res==1) { posB.push_back(i); posA.push_back(i+1); } else if(res==2) { posA.push_back(i); posB.push_back(i+1); } else { posA.push_back(i); posA.push_back(i+1); } } lst=i+1; } int ans=posA.size(); for(int i=lst+1;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...