Submission #419733

#	Time	Username	Problem	Language	Result	Execution time	Memory
419733		KoD	Counting Mushrooms (IOI20_mushrooms)	C++17	88.98 / 100	11 ms	452 KiB

mushrooms

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

template <class T> using Vec = std::vector<T>;

constexpr int NAIVE = 40;

int count_mushrooms(int n) {
	if (n <= 227) {
		int ret = 1;
		for (int i = 1; i < n; ++i) {
			ret += 1 - use_machine(Vec<int>{0, i});
		}
		return ret;
	}
	Vec<int> a, b;
	a.push_back(0);
	(use_machine(Vec<int>{0, 1}) ? b : a).push_back(1);
	(use_machine(Vec<int>{0, 2}) ? b : a).push_back(2);
	int seen = 3;
	if ((int) a.size() >= 2) {
		while ((int) std::max(a.size(), b.size()) < NAIVE) {
			Vec<int> ask;
			ask.push_back(seen);
			ask.push_back(a[0]);
			ask.push_back(seen + 1);
			ask.push_back(a[1]);
			const auto rsp = use_machine(ask);
			for (int k = 0; k < 2; ++k) {
				((rsp >> k & 1) ? b : a).push_back(seen + k);
			}
			seen += 2;
		}
	} else {
		while ((int) std::max(a.size(), b.size()) < NAIVE) {
			Vec<int> ask;
			ask.push_back(seen);
			ask.push_back(b[0]);
			ask.push_back(seen + 1);
			ask.push_back(b[1]);
			const auto rsp = use_machine(ask);
			for (int k = 0; k < 2; ++k) {
				((rsp >> k & 1) ? a : b).push_back(seen + k);
			}
			seen += 2;
		}
	}
	int ret = (int) a.size();
	while (seen < n) {
		if (a.size() > b.size()) {
			Vec<int> ask;
			for (int i = 0; i < (int) a.size() and seen < n; ++i) {
				ask.push_back(a[i]);
				ask.push_back(seen++);
			}
			const auto rsp = use_machine(ask);
			ret += (int) ask.size() / 2;
			ret -= (rsp + 1) / 2;
			(rsp % 2 == 0 ? a : b).push_back(ask.back());
		} else {
			Vec<int> ask;
			for (int i = 0; i < (int) b.size() and seen < n; ++i) {
				ask.push_back(b[i]);
				ask.push_back(seen++);
			}
			const auto rsp = use_machine(ask);
			ret += (rsp + 1) / 2;
			(rsp % 2 == 0 ? b : a).push_back(ask.back());
		}
	}
	return ret;
}

• Subtask 1: 88.9764 / 100