제출 #419734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419734		KoD	버섯 세기 (IOI20_mushrooms)	C++17	90.40 / 100	10 ms	440 KiB

mushrooms

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

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

constexpr int NAIVE = 50;

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: 90.4 / 100