| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 424239 | chirathnirodha | 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.
//Coded by Chirath Nirodha
#include "mushrooms.h"
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const ll mod=1e9+7;
int findbest(int n){
pair<int,int> x;
x.F=100000;
for(int i=0;i<1000;i++){
int temp=i+(2*(n-i-1)+i)/(i+1);
if(temp<x.F){
x.F=temp;
x.S=i;
}
}
return i;
}
int count_mushrooms(int n) {
vector<int> a,b;
a.push_back(0);
int cur=1;
int bb=best(n);
while(cur<n && cur<bb){
vector<int> m;
m.PB(0);m.PB(cur);
int x=use_machine(m);
if(x==0)a.PB(cur);
else b.PB(cur);
cur++;
}
int ac=a.size(),bc=b.size();
if(a.size()>=b.size()){
while(cur<n){
vector<int> m;
for(int i=0;i<a.size();i++){
m.PB(a[i]);
if(cur==n || i==a.size()-1)break;
m.PB(cur);
cur++;
}
int x=use_machine(m);
bc+=x/2;
}
return n-bc;
}
else{
while(cur<n){
vector<int> m;
for(int i=0;i<b.size();i++){
m.PB(b[i]);
if(cur==n || i==b.size()-1)break;
m.PB(cur);
cur++;
}
int x=use_machine(m);
ac+=x/2;
}
return ac;
}
}