Submission #1210082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210082		That_Salamander	Counting Mushrooms (IOI20_mushrooms)	C++20	56.78 / 100	3 ms	412 KiB

mushrooms

#include "mushrooms.h"

using namespace std;

#define START 101

/*
2 * START + (n - 2 * START) / (START - 1)

*/

int count_mushrooms(int n) {
	vector<int> knownAs, knownBs;
	knownAs.push_back(0);

	int pos = 1;

	while (pos < n && knownAs.size() < START && knownBs.size() < START) {
		int res = use_machine({0, pos});
		if (res == 0) knownAs.push_back(pos);
		else knownBs.push_back(pos);
		pos++;
	}

	int res = knownAs.size();

	while (pos < n) {
		int mushroomsInQuery = min(START - 1, n - pos);

		vector<int> query;

		bool isA = knownAs.size() >= START;

		for (int i = 0; i < mushroomsInQuery; i++) {
			if (isA) {
				query.push_back(knownAs[i]);
			} else {
				query.push_back(knownBs[i]);
			}

			query.push_back(pos++);
		}

		if (isA) {
			query.push_back(knownAs[mushroomsInQuery]);
		} else {
			query.push_back(knownBs[mushroomsInQuery]);
		}

		int qres = use_machine(query) / 2;
		
		if (isA) {
			res += mushroomsInQuery - qres;
		} else {
			res += qres;
		}
	}

	return res;
}

/*
B_B_B_B_B
*/

• Subtask 1: 56.7839 / 100