Submission #415821

#	Time	Username	Problem	Language	Result	Execution time	Memory
415821		SuhaibSawalha1	Counting Mushrooms (IOI20_mushrooms)	C++17	92.24 / 100	11 ms	508 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)a[0].size() < 2 && (int)a[1].size() < 2 && v.size();) {
		a[use_machine({0, v.back()})].push_back(v.back());
		v.pop_back();
	}
	int S = 70;
	int ind = a[1].size() > 1;
	for (; (int)a[0].size() <= S && (int)a[1].size() <= S && v.size() > 1;) {
		int res = use_machine({a[ind][0], v[v.size() - 2], a[ind][1], v.back()});
		a[(res < 2) ^ (!ind)].push_back(v[v.size() - 2]);
		a[(res % 2) ^ (ind)].push_back(v.back());
		v.pop_back();
		v.pop_back();
	}
	ans += a[0].size();
	while (v.size()) {
		int ind = a[0].size() < a[1].size();
		int use = min(a[ind].size(), v.size());
		vector<int> ask;
		for (int i = 0; i < 2 * use; ++i) {
			if (i & 1) {
				ask.push_back(v.back());
				v.pop_back();
			}
			else {
				ask.push_back(a[ind][i / 2]);
			}
		}
		int res = use_machine(ask);
		a[ind ^ (res & 1)].push_back(ask.back());
		if (ind) {
			ans += (res + 1) / 2;
		}
		else {
			ans += use - (res + 1) / 2;
		}
	}
	return ans;
}

• Subtask 1: 92.2449 / 100