제출 #1033325

#제출 시각아이디문제언어결과실행 시간메모리
1033325happy_node버섯 세기 (IOI20_mushrooms)C++17
65.70 / 100
6 ms604 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; const int B=200; 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...