제출 #388280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388280		JimmyZJX	버섯 세기 (IOI20_mushrooms)	C++14	92.62 / 100	10 ms	436 KiB

mushrooms

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>

using namespace std;

typedef long long LL;

#define MAXN 1048579 // 2^20+3

#define forR(i, n) for (int i = 0; i < (n); i++)

#ifdef TEST_LOCAL
int use_machine(vector<int> x) {
	return -1;
}
#else
int use_machine(vector<int> x);
#endif // TEST_LOCAL

int count_mushrooms(int n) {
	if (n < 200) {
		int cntA = 1;
		for (int i = 1; i < n; i++) {
			if (use_machine(vector<int>{0, i}) == 0)
				cntA++;
		}
		return cntA;
	}

	vector<int> As, Bs; As.push_back(0);

	int i = 1;
	while (As.size() < 2 && Bs.size() < 2) {
		int m = use_machine(vector<int>{0, i});
		if (m == 0) As.push_back(i);
		else Bs.push_back(i);
		i++;
	}

	while (i <= 160) {
		auto as = &As, bs = &Bs;
		if (As.size() < 2) swap(as, bs);
		int m = use_machine(vector<int>{ (*as)[0], i, (*as)[1], i + 1 });

		if ((m & 2) == 0) {
			as->push_back(i);
		} else {
			bs->push_back(i);
		}

		if ((m & 1) == 0) {
			as->push_back(i + 1);
		} else {
			bs->push_back(i + 1);
		}

		i += 2;
	}

	int cntA = 0;
	while (i < n) {
		int rest = n - i;
		auto as = &As, bs = &Bs;
		if (As.size() < Bs.size()) swap(as, bs); // as is larger

		int l = min(rest, (int)as->size());
		vector<int> test;
		for (int j = 0; j < l; j++) {
			test.push_back((*as)[j]);
			test.push_back(i + j);
		}
		int m = use_machine(test);

		if ((m & 1) == 0) {
			as->push_back(test.back());
		} else {
			bs->push_back(test.back());
		}

		int cnt_b = m / 2;
		int cnt_a = l - 1 - cnt_b;
		if ((*as)[0] == 0) {
			cntA += cnt_a;
		} else {
			cntA += cnt_b;
		}

		i += l;
	}

	return As.size() + cntA;
}

#ifdef TEST_LOCAL
vector<vector<int>> gen01Seq(int n) {
	if (n == 1) return vector<vector<int>>{ { 0 }, { 1 }};

	vector<vector<int>> all;
	vector<vector<int>> seqs = gen01Seq(n - 1);
	for (auto s : seqs) {
		s.push_back(0);
		all.push_back(s);
	}
	for (auto s : seqs) {
		s.push_back(1);
		all.push_back(s);
	}

	return all;
}

int calc(vector<int> ns) {
	int ans = 0;
	for (int i = 0; i < ns.size() - 1; i++) {
		if (ns[i] != ns[i + 1])
			ans++;
	}
	return ans;
}

int main() {
	auto s4 = gen01Seq(4);

	vector<vector<int>> alleq2;

	for (auto& s : s4) {
		if (calc(vector<int> { 0, s[0], s[1], s[2], s[3] }) == 2) {
			alleq2.push_back(s);
		}
	}

	int bestStep = 1000000, bestm = -1;
	for (int m = 60; m < 300; m++) {
		int step = m;
		int rest = 20000 - 2 * m;
		int k = m * 2;
		// got A*m
		while (rest > 0) {
			rest -= (k + 1) / 2; step++;
			k++;
		}
		if (step < bestStep) {
			bestStep = step;
			bestm = m;
		}
	}


	return 0;
}
#endif

• Subtask 1: 92.623 / 100