제출 #458009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
458009		rainboy	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	0 ms	200 KiB

mushrooms

#include "mushrooms.h"

using namespace std;

typedef vector<int> vi;

const int N = 141;

int aa[N * 2], bb[N * 2];

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 < N && nb < N)
		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 ((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 ((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;
	if (na > nb) {
		ans = n - nb;
		while (i < n) {
			ii.resize(0);
			for (h = 0; h < na; h++) {
				ii.push_back(aa[h]);
				if (i < n)
					ii.push_back(i++);
			}
			ans -= (use_machine(ii) + 1) / 2;
		}
	} else {
		ans = na;
		while (i < n) {
			ii.resize(0);
			for (h = 0; h < nb; h++) {
				ii.push_back(bb[h]);
				if (i < n)
					ii.push_back(i++);
			}
			ans += (use_machine(ii) + 1) / 2;
		}
	}
	return ans;
}

• Subtask 1: 0 / 100