Submission #1015612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015612		jairRS	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	2 ms	344 KiB

mushrooms

#include "mushrooms.h"
#include <iostream>
using namespace std;

int count_mushrooms(int n)
{
	if (n <= 226)
	{
		int ans = 0;
		for (int i = 1; i < n; i++)
		{
			int x = use_machine({0, i});
			if (x == 0)
				ans++;
		}

		return ans + 1;
	}

	// n > 226

	int x = 101;

	vector<int> A, B;
	for (int i = 1; i <= 2 * x; i++) // habia i += 2
	{
		int query = use_machine({0, i});
		if (query == 0)
			A.push_back(i);
		else
			B.push_back(i);
	}

	char big_group;
	vector<int> group;
	if (A.size() > B.size())
	{
		group = A;
		big_group = 'A';
	}
	else
	{
		group = B;
		big_group = 'B';
	}

	int ans = 0;
	for (int i = 2 * x + 1; i < n; i++)
	{
		vector<int> query = {group[0]}; // A ? A ? A ? A ? A ? A ? A
										// ^

		int next_mush = 1;
		int j = i;
		for (; j < i + x - 1; j++)
		{
			if (j >= n)
				break;

			query.push_back(j);
			query.push_back(group[next_mush]);
			next_mush++;
		}
		i = j;

		int res = use_machine(query);

		if (big_group == 'A')
			ans += (x - 1) - res / 2;
		else
			ans += res / 2;
	}

	return 1 + A.size() + ans;
}

• Subtask 1: 0 / 100