Submission #654017

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

mushrooms

#include "mushrooms.h"

int count_mushrooms(int n)
{
	std::vector < int > V0 = { 0 }, V1;
	int a1 = use_machine({ 0, 1 });
	if (n == 2)
		return 1 + a1;
	int unused = 2, Q = 1;
	if (a1)
	{
		V1.push_back(1);
		int a2 = use_machine({ 0, 2 });
		if (a2)
			V1.push_back(2);
		else
			V0.push_back(2);
		unused++;
		Q++;
	}
	else
		V0.push_back(1);
	while (Q < 82)
	{
		if (unused == n)
			return V0.size();
		if (unused == n - 1)
			return V0.size() + use_machine({ 0, n - 1 });
		if (V0.size() >= 2)
		{
			int r = use_machine({ V0[0], unused, V0[1], unused + 1 });
			if (r & 2)
				V1.push_back(unused);
			else
				V0.push_back(unused);
			if (r & 1)
				V1.push_back(unused + 1);
			else
				V0.push_back(unused + 1);
			unused += 2;
		}
		else
		{
			int r = use_machine({ V1[0], unused, V1[1], unused + 1 });
			if (r & 2)
				V0.push_back(unused);
			else
				V1.push_back(unused);
			if (r & 1)
				V0.push_back(unused + 1);
			else
				V1.push_back(unused + 1);
			unused += 2;
		}
		Q++;
	}
	int O = V0.size();
	while (true)
	{
		std::vector < int > query;
		if (V0.size() >= V1.size())
		{
			if (n - unused > V0.size())
			{
				for (int i = 0; i < V0.size(); i++)
				{
					query.push_back(V0[i]);
					query.push_back(unused + i);
				}
				int r = use_machine(query);
				O += V0.size() - (r + 1 >> 1);
				if (r & 1)
					V1.push_back(unused + V0.size() - 1);
				else
					V0.push_back(unused + V0.size() - 1);
				unused += V0.size();
			}
			else
			{
				int L = n - unused;
				for (int i = 0; i < L; i++)
				{
					query.push_back(V0[i]);
					query.push_back(unused + i);
				}
				return O + L - (use_machine(query) + 1 >> 1);
			}
		}
		else
		{
			if (n - unused > V1.size())
			{
				for (int i = 0; i < V1.size(); i++)
				{
					query.push_back(V0[i]);
					query.push_back(unused + i);
				}
				int r = use_machine(query);
				O += r + 1 >> 1;
				if (r & 1)
					V0.push_back(unused + V1.size() - 1);
				else
					V1.push_back(unused + V1.size() - 1);
				unused += V1.size();
			}
			else
			{
				int L = n - unused;
				for (int i = 0; i < L; i++)
				{
					query.push_back(V1[i]);
					query.push_back(unused + i);
				}
				return O + (use_machine(query) + 1 >> 1);
			}
		}
	}
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    if (n - unused > V0.size())
      |        ~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < V0.size(); i++)
      |                     ~~^~~~~~~~~~~
mushrooms.cpp:71:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     O += V0.size() - (r + 1 >> 1);
      |                       ~~^~~
mushrooms.cpp:86:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     return O + L - (use_machine(query) + 1 >> 1);
      |                     ~~~~~~~~~~~~~~~~~~~^~~
mushrooms.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    if (n - unused > V1.size())
      |        ~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < V1.size(); i++)
      |                     ~~^~~~~~~~~~~
mushrooms.cpp:99:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     O += r + 1 >> 1;
      |          ~~^~~
mushrooms.cpp:114:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |     return O + (use_machine(query) + 1 >> 1);
      |                 ~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 100