Submission #412917

#	Time	Username	Problem	Language	Result	Execution time	Memory
412917		SuhaibSawalha1	Counting Mushrooms (IOI20_mushrooms)	C++17	75.59 / 100	12 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)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 = 100;
	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();
	}
	while (v.size()) {
		int use = min((int)v.size(), S);
		int ind = (int)a[1].size() > use;
		vector<int> ask;
		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: 75.5853 / 100