Submission #720668

#	Time	Username	Problem	Language	Result	Execution time	Memory
720668		jairRS	Counting Mushrooms (IOI20_mushrooms)	C++17	25 / 100	87 ms	220 KiB

mushrooms

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

int count_mushrooms(int n)
{
	int count = 1;

	// X A X - good

	// A X A X A X

	if (n <= 5)
	{
		for (int i = 1; i < n; i++)
			count += 1 - use_machine({0, i});

		return count;
	}

	vector<int> As = {0};
	vector<int> Bs = {};

	for (int i = 1; i <= 5; i++)
	{
		int query = use_machine({0, i});
		if (query)
			Bs.push_back(i);
		else
			As.push_back(i);
	}

	count += As.size() - 1;

	// case 1: three As
	if (As.size() >= 3)
	{
		int i = 6;
		for (; i + 2 < n; i += 3)
		{
			int query = use_machine({0, i, As[1], i + 1, As[2], i + 2});

			int amountOfB = query / 2 + query % 2;
			count += 3 - amountOfB;
		}

		for (; i < n; i++)
			count += 1 - use_machine({0, i});
	}
	else
	{
		int i = 6;
		for (; i + 2 < n; i += 3)
		{
			int query = use_machine({Bs[0], i, Bs[1], i + 1, Bs[2], i + 2});

			int amountOfA = query / 2 + query % 2;
			count += amountOfA;
		}

		for (; i < n; i++)
			count += 1 - use_machine({0, i});
	}

	return count;
}

• Subtask 1: 25 / 100