Submission #411748

#	Time	Username	Problem	Language	Result	Execution time	Memory
411748		SuhaibSawalha1	Counting Mushrooms (IOI20_mushrooms)	C++17	56.78 / 100	14 ms	456 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

int count_mushrooms(int n) {
	int ans = 0;
	vector<int> a[2], v(n - 1);
	iota(v.begin(), v.end(), 1);
	a[0] = {0};
	for (int i = 1; a[0].size() <= 100 && a[1].size() <= 100 && i < min(n, 201); ++i) {
		a[use_machine({0, v.back()})].push_back(v.back());
		v.pop_back();
	}
	while (v.size()) {
		int use = min((int)v.size(), 100);
		vector<int> ask;
		int ind = (int)a[1].size() > use;
		for (int i = 0; i < 2 * use + 1; ++i) {
			if (i & 1) {
				ask.push_back(v.back());
				v.pop_back();
			}
			else {
				ask.push_back(a[ind][i / 2]);
			}
		}
		if (ind) {
			ans += use_machine(ask) / 2;
		}
		else {
			ans += use - use_machine(ask) / 2;
		}
	}
	return ans + a[0].size();
}

• Subtask 1: 56.7839 / 100