Submission #1230517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230517		kaltspielerhy	Counting Mushrooms (IOI20_mushrooms)	C++20	55.53 / 100	3 ms	428 KiB

mushrooms

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

int count_mushrooms(int n) {
	vector<int> m, a, b;
	m.push_back(0);
	a.push_back(0);
	int fin = 1;
	for (int i = 1; i < n; i++) {
		m.push_back(i);
		int res = use_machine(m);
		if (res == 0) a.push_back(i);
		else b.push_back(i);
		m.pop_back();

		fin++;
		if (a.size() > n/160 || b.size() > n/160) break;
	}
	
	vector<int> majo = (a.size() > b.size() ? a : b);
	int ans;
	if (a.size() > b.size()) ans = b.size();
	else ans = a.size();
	while (fin != n) {
		int idx = 0;
		vector<int> rq;
		while (idx < majo.size() && fin != n) {
			rq.push_back(fin);
			rq.push_back(majo[idx]);
			fin++;
			idx++;
		}

		ans += (use_machine(rq)+1)/2;
	}

	if (a.size() > b.size()) return n-ans;
	else return ans;
}

• Subtask 1: 55.5283 / 100