Submission #828696

#	Time	Username	Problem	Language	Result	Execution time	Memory
828696		Minindu206	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	1 ms	208 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n)
{
	vector<int> posa, posb, pos;
	int acnt = 1, bcnt = 0, cnt, ans = 1;
	posa.push_back(0);
	if (n <= 170)
	{
		for (int i = 1; i < min(170, n); i++)
		{
			int cur = use_machine({0, i});
			if (cur == 0)
			{
				posa.push_back(i);
				acnt++;
				ans++;
			}
			else
			{
				posb.push_back(i);
				bcnt++;
			}
		}
		return ans;
	}
	if (use_machine({0, 1}))
		posb.push_back(1), acnt++, ans++;
	else
		posa.push_back(1), bcnt++;
	if (use_machine({0, 2}))
		posb.push_back(2), acnt++, ans++;
	else
		posa.push_back(2), bcnt++;

	int c = 0;
	if (acnt >= bcnt)
		pos = posa, c = 1;
	else
		pos = posb;
	for (int i = 3; i < 170; i += 2)
	{
		int cur = use_machine({pos[0], i, pos[1], i + 1});
		if (c)
			ans += (cur - ((cur + 1) / 2));
		else
			ans += (cur + 1) / 2;

		if (c)
		{
			if (cur == 1)
			{
				posb.push_back(i + 1);
				posa.push_back(i);
				acnt++, bcnt++;
			}
			else if (cur == 2)
			{
				posb.push_back(i);
				posa.push_back(i + 1);
				acnt++, bcnt++;
			}
			else if (cur == 3)
			{
				posb.push_back(i);
				posb.push_back(i + 1);
				bcnt += 2;
			}
			else
			{
				posa.push_back(i);
				posa.push_back(i + 1);
				acnt += 2;
			}
		}
		else
		{
			if (cur == 2)
			{
				posb.push_back(i + 1);
				posa.push_back(i);
				acnt++, bcnt++;
			}
			else if (cur == 1)
			{
				posb.push_back(i);
				posa.push_back(i + 1);
				acnt++, bcnt++;
			}
			else if (cur == 0)
			{
				posb.push_back(i);
				posb.push_back(i + 1);
				bcnt += 2;
			}
			else
			{
				posa.push_back(i);
				posa.push_back(i + 1);
				acnt += 2;
			}
		}
	}
	if (acnt >= bcnt)
		pos = posa;
	else
		pos = posb;

	int i = 170;

	vector<int> chk;
	while (i < n)
	{
		chk.clear();
		int cur = 0, vr = i + pos.size();
		for (; i < min(vr, n) && cur < pos.size(); i++)
		{
			chk.push_back(i);
			chk.push_back(pos[cur]);
			cur++;
		}
		int ncur = use_machine(chk);
		if (acnt >= bcnt)
			ans += (cur - ((cur + 1) / 2));
		else
			ans += (cur + 1) / 2;
	}
	return n - ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:117:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   for (; i < min(vr, n) && cur < pos.size(); i++)
      |                            ~~~~^~~~~~~~~~~~
mushrooms.cpp:123:7: warning: unused variable 'ncur' [-Wunused-variable]
  123 |   int ncur = use_machine(chk);
      |       ^~~~
mushrooms.cpp:7:26: warning: unused variable 'cnt' [-Wunused-variable]
    7 |  int acnt = 1, bcnt = 0, cnt, ans = 1;
      |                          ^~~

• Subtask 1: 0 / 100