# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1235211 | stanirina | Counting Mushrooms (IOI20_mushrooms) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
//#include "mushrooms.h"
using namespace std;
int count_mushrooms(int n) {
int ans=1;
vector<int> a;
vector<int> b;
a.clear();
b.clear();
a.push_back(0);
for (int i = 1; i < min(n,200); i++){
int c=use_machine({i,0});
if(c==0)a.push_back(i);
else b.push_back(i);
}
ans=a.size();
vector<int> m;
int sz=200;
for(int i=200;i<n;i+=200){
m.clear();
int j=i;
for(j;j<min(n,i+(int)a.size());j++){
m.push_back(a[j-i]);
m.push_back(j);
}
if(m.size()>0)ans+=(a.size()-(use_machine(m)+1)/2);
m.clear();
for(j;j<min(n,i+200);j++){
m.push_back(b[j-i-a.size()]);
m.push_back(j);
}
if(m.size()>0)ans+=(use_machine(m)+1)/2;
}
return ans;
}