Submission #305733

#	Time	Username	Problem	Language	Result	Execution time	Memory
305733		arthurconmy	Counting Mushrooms (IOI20_mushrooms)	C++14	56.93 / 100	12 ms	512 KiB

mushrooms

#ifndef ARTHUR_LOCAL
	#include "mushrooms.h"
#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define len(x) int((x).size())

#ifdef ARTHUR_LOCAL
int use_machine(vector<int> V)
{
	for(auto v:V)
	{
		cout << v << " ";
	}
	cout << endl;

	if(V[1] == 3) return 1;
	if(V[1] == 2) return 0;
	if(V[1] == 1) return 1;

	int x;
	cin>>x;

	return x;
}
#endif

int count_mushrooms(int n) 
{
	vector<int> indices;
	for(int i=1; i<n; i++) indices.push_back(i);

	vector<int> As;
	vector<int> Bs;

	for(int i=1; i<=200 && !indices.empty(); i++)
	{
		int cur = use_machine({0,indices.back()});

		if(cur==1) Bs.push_back(indices.back());
		else As.push_back(indices.back());

		indices.pop_back();
	}

	int no_As = len(As) + 1;

	if(len(As)>=len(Bs))
	{
		// reverse(As.begin(),As.end());
		// As.push_back(0);
		// reverse(As.begin());

		while(!indices.empty())
		{
			vector<int> cur;

			while(!indices.empty() && len(cur) <= len(As))
			{
				cur.push_back(indices.back());
				indices.pop_back();
			}

			vector<int> req = {0};
		
			for(int i=0; i<len(cur); i++)
			{
				req.push_back(cur[i]);
				if(i<len(As)) req.push_back(As[i]);
			}

			int curbs = int((use_machine(req)+1)/2);
			no_As += len(cur) - curbs;

			// return -1;
		}

		return no_As;
	}

	else
	{
		while(!indices.empty())
		{
			vector<int> cur;

			while(!indices.empty() && len(cur) < len(Bs))
			{
				cur.push_back(indices.back());
				indices.pop_back();
			}

			vector<int> req = {0};

			for(int i=0; i<len(cur); i++)
			{
				req.push_back(Bs[i]);
				req.push_back(cur[i]);
			}

			no_As += int((use_machine(req))/2);
		}

		return no_As;
	}
}

#ifdef ARTHUR_LOCAL
int main()
{
	cout << "ANS: " << count_mushrooms(4) << endl;
}
#endif

• Subtask 1: 56.927 / 100