Submission #419702

#	Time	Username	Problem	Language	Result	Execution time	Memory
419702		KoD	Counting Mushrooms (IOI20_mushrooms)	C++17	78.75 / 100	13 ms	456 KiB

mushrooms

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

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

constexpr int NAIVE = 60;

int count_mushrooms(int n) {
	Vec<int> a, b;
	a.push_back(0);
	for (int i = 1; i < std::min(n, NAIVE); ++i) {
		(use_machine(Vec<int>{0, i}) ? b : a).push_back(i);
	}
	int ret = (int) a.size();
	int seen = std::min(n, NAIVE);
	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: 78.7456 / 100