# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
305927 | myungwoo | Counting Mushrooms (IOI20_mushrooms) | C++17 | 11 ms | 384 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>
#include "mushrooms.h"
using namespace std;
int count_mushrooms(int N)
{
int iter = 71;
vector<int> arr[2] = {{0}, {}};
int pt = 1;
// Step 1: Check type of mushroom one by one
while (pt < N){
arr[use_machine({0, pt})].push_back(pt);
pt++;
if (arr[0].size() >= 2 || arr[1].size() >= 2) break;
}
// Step 2: Check type of mushroom two by one
while (pt < N){
int t = arr[1].size() >= 2;
vector<int> test = {arr[t][0], pt, arr[t][1]};
if (pt+1 < N) test.push_back(pt+1);
int res = use_machine(test);
arr[res>>1&1^t].push_back(pt);
if (pt+1 < N) arr[res&1^t].push_back(pt+1);
pt += 2;
if (!--iter) break;
}
// Step 3: Count number of type 0 mushrooms s by one
int zero_count = arr[0].size();
while (pt < N){
int t = arr[1].size() > arr[0].size();
vector<int> test;
for (int i=0;pt+i<N&&i<arr[t].size();i++){
test.push_back(arr[t][i]);
test.push_back(pt+i);
}
int res = use_machine(test);
arr[res&1^t].push_back(test.back());
int cnt = res+1>>1;
if (!t) cnt = test.size()/2-cnt;
zero_count += cnt;
pt += test.size()/2;
}
return zero_count;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |