# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1066108 | Ahmed57 | Counting Mushrooms (IOI20_mushrooms) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
int count_mushrooms(int n){
int B = 417;
vector<int> BS;
int cnt = 0;
vector<int> pending;
for(int i = 0;i<n;i+=B){
vector<int> v;
if(i!=0)v.push_back(0);
for(int j = i;j<min(n,i+B);j++)v.push_back(j);
if(use_machine(v)==0){
cnt+=(min(i+B,n)-i);
continue;
}
int l = max(1,i) , r =min(n-1,i+B-1) , ans = -1;
while(l<=r){
vector<int> v;
int mid = (l+r)/2;
if(i!=0)v.push_back(0);
for(int j = i;j<=mid;j++){
v.push_back(j);
}
if(use_machine(v)!=0){
ans = mid;
r = mid-1;
}else l = mid+1;
}
BS.push_back(ans);
for(int j = ans+1;j<min(n,i+B);j++){
pending.push_back(j);
}
cnt+=ans-i;
}
int sz = BS.size();
int sz2 = pending.size();
for(int i = 0;i<pending.size();i+=sz){
int xd = i;
vector<int> lol;
for(int j = i;j<min(sz2,i+sz);j++){
lol.push_back(BS[j-i]);
lol.push_back(pending[j]);
}
int ans = use_machine(lol);
if(ans%2){
cnt++;
ans--;
}
ans/=2;
cnt+=ans;
}
return cnt;
}