| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1313704 | PlayVoltz | Counting Mushrooms (IOI20_mushrooms) | C++20 | 0 ms | 0 KiB |
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int X=100;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int count_mushrooms(int n){
vector<int> ord;
for (int i=1; i<n; ++i)ord.pb(i);
vector<vector<int> > vect(2);
vect[0].pb(0);//
if (n<=227){
int res=1;
for (int i=1; i<n; ++i)res+=!use_machine({0, i});
return res;
}
while (max(vect[0].size(), vect[1].size())<X){
if (use_machine({0, ord.back()}))vect[1].pb(ord.back());
else vect[0].pb(ord.back());
ord.pop_back();
}
//while ()
int ans=vect[0].size();
while (p<n){
int id=0;
if (vect[0].size()<vect[1].size())id=1;
vector<int> temp;
for (int i=0; i<vect[id].size()&&ord.size(); ++i)temp.pb(vect[id][i]), temp.pb(ord.back()), ord.pop_back();
int res=use_machine(temp);
if (id)ans+=res/2+res%2;
else ans+=temp.size()/2-(res/2+res%2);
if (res%2)vect[!id].pb(p-1);
else vect[id].pb(p-1);
}
return ans;
}
