Submission #781053

#	Time	Username	Problem	Language	Result	Execution time	Memory
781053		Josia	Counting Mushrooms (IOI20_mushrooms)	C++17	56.93 / 100	8 ms	336 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

int count_mushrooms(int n) {
	vector<int> is = {0}, isnot;

	int pos = 1;

	const int reqsize = 107;

	while(pos < n && is.size()<reqsize && isnot.size()<reqsize) {
		if (use_machine({0, pos})) isnot.push_back(pos);
		else is.push_back(pos);

		pos++;
	}

	if (is.size() > isnot.size()) {
		int res = is.size();
		for (int i = pos; i<n; i+=is.size()) {
		vector<int> check;
			for (int j = i; j<min(n, (int)(i+is.size())); j++) {
				check.push_back(is[j-i]);
				check.push_back(j);
			}
			int ans;
			if (check.empty()) ans = 0;

			else ans = use_machine(check);

			res += check.size()/2 - (ans+1)/2;
		}
		return res;
	}

	else {
		int res = isnot.size();
		for (int i = pos; i<n; i+=isnot.size()) {
		vector<int> check;
			for (int j = i; j<min(n, (int)(i+isnot.size())); j++) {
				check.push_back(isnot[j-i]);
				check.push_back(j);
			}
			int ans;
			if (check.empty()) ans = 0;

			else ans = use_machine(check);

			res += check.size()/2 - (ans+1)/2;

		}
		res = n-res;
		return res;
	}
}

• Subtask 1: 56.927 / 100