Submission #830990

#	Time	Username	Problem	Language	Result	Execution time	Memory
830990		pavement	Counting Mushrooms (IOI20_mushrooms)	C++17	90.04 / 100	8 ms	468 KiB

mushrooms

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

#define pb push_back

const int k = 223;

int count_mushrooms(int n) {
	vector<int> m(n);
	if (n <= k) {
		for (int i = 1; i < n; i++) {
			m[i] = use_machine({0, i});
		}
		return count(m.begin(), m.end(), 0);
	}
	m[1] = use_machine({0, 1});
	m[2] = use_machine({0, 2});
	vector<int> sm;
	if (!m[1]) {
		sm = {0, 1};
	} else if (!m[2]) {
		sm = {0, 2};
	} else {
		sm = {1, 2};
	}
	for (int i = 3; i + 1 < k; i += 2) {
		int x = use_machine({sm[0], i, sm[1], i + 1});
		if (x == 0) {
			m[i] = m[i + 1] = m[sm[0]];
		} else if (x == 1) {
			m[i] = m[sm[0]];
			m[i + 1] = !m[sm[0]];
		} else if (x == 2) {
			m[i] = !m[sm[0]];
			m[i + 1] = m[sm[0]];
		} else if (x == 3) {
			m[i] = m[i + 1] = !m[sm[0]];
		}
	}
	int dom;
	if (count(m.begin(), m.begin() + k, 0) > count(m.begin(), m.begin() + k, 1)) dom = 0;
	else dom = 1;
	sm.clear();
	for (int i = 0; i < k; i++) {
		if (m[i] == dom) {
			sm.pb(i);
		}
	}
	int ans = count(m.begin(), m.begin() + k, 0);
	for (int i = k; i < n; ) {
		vector<int> cur;
		for (int j = i; j < min(n, i + (int)sm.size()); j++) {
			cur.pb(j);
			cur.pb(sm[j - i]);
		}
		int tmp = use_machine(cur);
		if (tmp % 2 == 0) {
			sm.pb(i);
		}
		int diff = (tmp + 1) / 2;
		if (dom == 0) {
			ans += (int)cur.size() / 2 - diff;
		} else {
			ans += diff;
		}
		i += (int)cur.size() / 2;
	}
	return ans;
}

• Subtask 1: 90.0398 / 100