# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1035705 | Mr_Husanboy | Counting Mushrooms (IOI20_mushrooms) | C++17 | 7 ms | 600 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 "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
template<typename T>
int len(T &a){return a.size();}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int count_mushrooms(int n) {
if(n < 10){
int ans = 1;
for(int i = 1; i < n; i ++){
ans += use_machine({0, i}) ^ 1;
}
return ans;
}
int sq = sqrt(n);
int i = 1;
vector<int> a = {0}, b;
while(len(a) < sq && len(b) < sq){
if(use_machine({0, i})){
b.push_back(i);
}else{
a.push_back(i);
}
i ++;
}
if(len(a) >= sq){
ll ans = len(a);
while(i < n){
vector<int> req;
for(int j = 0; j < len(a) && i < n; j ++){
req.push_back(a[j]);
req.push_back(i);
i ++;
}
// for(auto u : req) cout << u << ' ';
// cout << endl;
ans += len(req) / 2 - (use_machine(req) + 1) / 2;
}
return ans;
}else{
ll ans = len(a);
while(i < n){
vector<int> req;
for(int j = 0; j < len(b) && i < n; j ++){
req.push_back(b[j]);
req.push_back(i);
i ++;
}
ans += (use_machine(req) + 1) / 2;
}
return ans;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |