제출 #654018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654018		ellakass	버섯 세기 (IOI20_mushrooms)	C++14	0 / 100	2 ms	212 KiB

mushrooms

#include <cstdio>
#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() + 1 - 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);
			}
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 100