Submission #882291

#	Time	Username	Problem	Language	Result	Execution time	Memory
882291		pirhosig	Counting Mushrooms (IOI20_mushrooms)	C++17	89.33 / 100	6 ms	876 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
#define  R(a) for (int i = 0; i < a; ++i)
#define RR(a) for (int j = 0; j < a; ++j)
using namespace std;



int count_mushrooms(int n)
{
	if (n < 200)
	{
		int tot = 1;
		for (int i = 1; i < n; ++i)
		{
			tot += 1 - use_machine({0, i});
		}
		return tot;
	}

	vector<int> ta;
	vector<int> tb;
	ta.push_back(0);

	R(2)
	{
		if (use_machine({0, i + 1})) tb.push_back(i + 1);
		else ta.push_back(i + 1);
	}

	int up = 3;

	R(40)
	{
		int n1 = up++;
		int n2 = up++;
		if (ta.size() > tb.size())
		{
			int qres = use_machine({ta[0], n1, ta[1], n2});
			if (qres / 2) tb.push_back(n1);
			else ta.push_back(n1);
			if (qres % 2) tb.push_back(n2);
			else ta.push_back(n2);
		}
		else
		{
			int qres = use_machine({tb[0], n1, tb[1], n2});
			if (qres / 2) ta.push_back(n1);
			else tb.push_back(n1);
			if (qres % 2) ta.push_back(n2);
			else tb.push_back(n2);
		}
	}

	int tot = 0;

	while (up < n)
	{
		int rem = n - up;
		int s1 = ta.size();
		int s2 = tb.size();
		if (s1 > s2)
		{
			vector<int> query;
			int qs = min(rem, s1);
			R(qs * 2)
			{
				if (i % 2) query.push_back(up++);
				else query.push_back(ta[i / 2]);
			}
			int qres = use_machine(query);
			if (qres % 2) tb.push_back(up - 1);
			else ta.push_back(up - 1);
			tot += qs - 1 - (qres / 2);
		}
		else
		{
			vector<int> query;
			int qs = min(rem, s2);
			R(qs * 2)
			{
				if (i % 2) query.push_back(up++);
				else query.push_back(tb[i / 2]);
			}
			int qres = use_machine(query);
			if (qres % 2) ta.push_back(up - 1);
			else tb.push_back(up - 1);
			tot += qres / 2;
		}
	}

	return tot + ta.size();
}

• Subtask 1: 89.3281 / 100