oj.uz

Submission #1015612

# Submission time Handle Problem Language Result Execution time Memory
1015612 2024-07-06T15:20:42 Z jairRS Counting Mushrooms (IOI20_mushrooms) C++17
0 / 100
 2 ms 344 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 2 ms 344 KB Answer is not correct.
7 Halted 0 ms 0 KB -