Submission #1042635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042635		DorostWef	Counting Mushrooms (IOI20_mushrooms)	C++17	80.43 / 100	8 ms	692 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

int count_mushrooms(int n) {
	vector <int> a;
	for (int i = 1; i < n; i++)
		a.push_back(i);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	shuffle(a.begin(), a.end(), rng);
	if (n >= 100)
		use_machine (a);
	int ans = 1;
	vector <int> A = {0}, B;
	while (!a.empty()) {
		vector <int> v;
		if ((int)A.size() >= (int)B.size()) {
			int t = 0;
			for (int i = 0; i < (int) A.size() && !a.empty(); i++) {
				t++;
				v.push_back(a.back());
				v.push_back(A[i]);
				a.pop_back();
			}
			int k = use_machine (v);
			if (k % 2)
				B.push_back(v[0]);
			else
				A.push_back(v[0]);
			k = t - ((k + 1) / 2);
			ans += k;
		} else {
			int t = 0;
			for (int i = 0; i < (int) B.size() && !a.empty(); i++) {
				t++;
				v.push_back(a.back());
				v.push_back(B[i]);
				a.pop_back();
			}
			int k = use_machine (v);
			if (k % 2)
				A.push_back(v[0]);
			else
				B.push_back(v[0]);
			k = ((k + 1) / 2);
			ans += k;
		}
	}
	return ans;
}

• Subtask 1: 80.427 / 100