Submission #1136743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136743		vjudge2	Counting Mushrooms (IOI20_mushrooms)	C++20	61.25 / 100	3 ms	428 KiB

mushrooms

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

const int K = 200;

int count_mushrooms(int n) {
	if (n <= 2000) {
		int cnt = 1;
		vector<int> a, b;
		a.push_back(0);
		int mx = 0;
		for (int i = 1; i < n; i++) {
			vector<int> m = {0, i};
			int res = use_machine(m);
			if (!res) cnt++, a.push_back(i);
			else b.push_back(i);
			++mx;
			if (a.size() >= 100 || b.size() >= 100) break;
		}
		bool f = 0;
		if (a.size() < b.size()) f = 1, swap(a, b);
		int sz = a.size();
		// for (int i : b) t.push_back(i);
		for (int i = mx + 1; i < n; i += sz - 1) {
			vector<int> v;
			int it = 0, tested = 0;
			for (int j = i; j <= min(n-1, i + sz-1 - 1); j++) {
				v.push_back(a[it++]);
				v.push_back(j);
				tested++;
			}
			while (it < a.size()) v.push_back(a[it++]);
			int res = use_machine(v);
			if (!f) cnt += (tested - res / 2);
			else cnt += (res / 2);
		}
		return cnt;
	}
	int cnt = 1;
	vector<int> a, b;
	a.push_back(0);
	int mx = 0;
	for (int i = 1; i < n; i += 3) {
		vector<int> m = {0, i, i+1, i+2};
		int res = use_machine(m);
		if (!res) {
			cnt += 3;
			a.push_back(i); a.push_back(i+1); a.push_back(i+2);
		} else if (res == 3) {
			cnt += 1;
			b.push_back(i); a.push_back(i+1); b.push_back(i+2);
		} else if (res == 1) {
			b.push_back(i+2);
			vector<int> m = {0, i};
			res = use_machine(m);
			if (res) {
				b.push_back(i);
				b.push_back(i+1);
			} else {
				cnt++;
				a.push_back(i);
				m = {0, i+1};
				res = use_machine(m);
				if (!res) {
					cnt++;
					a.push_back(i+1);
				} else b.push_back(i+1);
			}
		} else if (res == 2) {
			cnt++;
			a.push_back(i+2);
			vector<int> m = {0, i};
			res = use_machine(m);
			if (!res) {
				cnt++;
				a.push_back(i);
				b.push_back(i+1);
			} else {
				b.push_back(i);
				m = {0, i+1};
				res = use_machine(m);
				if (!res) {
					cnt++;
					a.push_back(i+1);
				} else {
					b.push_back(i+1);
				}
			}
		}
		mx += 3;
		if (a.size() >= 150 || b.size() >= 150) break;
	}
	bool f = 0;
	if (a.size() < b.size()) f = 1, swap(a, b);
	int sz = a.size();
	// for (int i : b) t.push_back(i);
	for (int i = mx + 1; i < n; i += sz - 1) {
		vector<int> v;
		int it = 0, tested = 0;
		for (int j = i; j <= min(n-1, i + sz-1 - 1); j++) {
			v.push_back(a[it++]);
			v.push_back(j);
			tested++;
		}
		while (it < a.size()) v.push_back(a[it++]);
		int res = use_machine(v);
		if (!f) cnt += (tested - res / 2);
		else cnt += (res / 2);
	}
	return cnt;
}

• Subtask 1: 61.2466 / 100