Submission #458041

#	Time	Username	Problem	Language	Result	Execution time	Memory
458041		rainboy	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	10 ms	432 KiB

mushrooms

#include "mushrooms.h"

using namespace std;

typedef vector<int> vi;

const int N = 20000, B = 80;

int aa[N], bb[N];

int count_mushrooms(int n) {
	vi ii;
	int na, nb, h, i, x, ans;

	i = 1, na = nb = 0;
	aa[na++] = 0;
	while (i < n && na < B && nb < B)
		if (na >= 2) {
			ii.resize(0);
			ii.push_back(aa[0]), ii.push_back(i), ii.push_back(aa[1]);
			if (i + 1 < n)
				ii.push_back(i + 1);
			x = use_machine(ii);
			if ((x & 2) == 0)
				aa[na++] = i;
			else
				bb[nb++] = i;
			if (i + 1 < n) {
				if ((x & 1) == 0)
					aa[na++] = i + 1;
				else
					bb[nb++] = i + 1;
			}
			i += 2;
		} else if (nb >= 2) {
			ii.resize(0);
			ii.push_back(bb[0]), ii.push_back(i), ii.push_back(bb[1]);
			if (i + 1 < n)
				ii.push_back(i + 1);
			x = use_machine(ii);
			if ((x & 2) == 0)
				bb[nb++] = i;
			else
				aa[na++] = i;
			if (i + 1 < n) {
				if ((x & 1) == 0)
					bb[nb++] = i + 1;
				else
					aa[na++] = i + 1;
			}
			i += 2;
		} else {
			ii.resize(0);
			ii.push_back(0), ii.push_back(i);
			if (use_machine(ii) == 0)
				aa[na++] = i;
			else
				bb[nb++] = i;
			i++;
		}
	if (i >= n)
		return na;
	ans = na;
	while (i < n) {
		int n_;

		if (na > nb) {
			ii.resize(0);
			for (h = 0; h < na; h++) {
				ii.push_back(aa[h]);
				if (i < n)
					ii.push_back(i++);
			}
			n_ = ii.size();
			x = use_machine(ii);
			if (n_ == na * 2) {
				if (x % 2 == 1)
					bb[nb++] = ii[--n_], x--;
				else
					aa[na++] = ii[n_ - 1], ans++;
			}
			ans += n_ - na - x / 2;
		} else {
			ii.resize(0);
			for (h = 0; h < nb; h++) {
				ii.push_back(bb[h]);
				if (i < n)
					ii.push_back(i++);
			}
			n_ = ii.size();
			x = use_machine(ii);
			if (n_ == nb * 2) {
				if (x % 2 == 1)
					aa[na++] = ii[--n_], ans++, x--;
				else
					bb[nb++] = ii[n_ - 1];
			}
			ans += x / 2;
		}
	}
	return ans;
}

• Subtask 1: 92.623 / 100