제출 #419678

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

mushrooms

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

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

int count_mushrooms(int n) {
	Vec<int> a, b;
	a.push_back(0);
	for (int i = 1; i < std::min(n, 200); ++i) {
		(use_machine(Vec<int>{0, i}) ? b : a).push_back(i);
	}
	bool flip = false;
	if (a.size() < b.size()) {
		flip = true;
		std::swap(a, b);
	}
	const int len = (int) a.size();
	int ret = len;
	int seen = std::min(n, 200);
	while (seen < n) {
		Vec<int> ask;
		for (int i = 0; i < len and seen < n; ++i) {
			ask.push_back(a[i]);
			ask.push_back(seen++);
		}
		ret += (int) ask.size() / 2;
		ret -= (use_machine(ask) + 1) / 2;
	}
	return flip ? n - ret : ret;
}

• Subtask 1: 56.927 / 100