Submission #377794

#TimeUsernameProblemLanguageResultExecution timeMemory
377794autumn_eelCounting Mushrooms (IOI20_mushrooms)C++14
0 / 100
0 ms364 KiB
#include "mushrooms.h" #include <bits/stdc++.h> #define rep(i,n)for(int i=0;i<int(n);i++) using namespace std; typedef long long ll; int count_mushrooms(int n) { int Min=INT_MAX; int M=-1; for(int N=1;N<=n;N++){ int c=N+2*(n-N)/N; if(Min>c){ M=N; Min=c; } } //~ cout<<Min<<' '<<M<<endl; vector<int>black,white; black.push_back(0); for(int i=1;i<M;i++){ vector<int>v={0,i}; int c=use_machine(v); if(c==0)black.push_back(i); else white.push_back(i); } vector<int>idx=(black.size()>white.size()?black:white); int ans=0; int rest=n-M; int cur=M; while(rest){ int d=min(rest,(int)idx.size()-1); vector<int>v; rep(i,d){ v.push_back(idx[i]); v.push_back(cur+i); } v.push_back(idx.back()); int c=use_machine(v); assert(c%2==0); ans+=c/2; cur+=d; rest-=d; } if(black.size()>white.size()){ return n-(white.size()+ans); } else{ return black.size()+ans; } }
#Verdict Execution timeMemoryGrader output
Fetching results...