제출 #654044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654044		ellakass	버섯 세기 (IOI20_mushrooms)	C++14	100 / 100	9 ms	316 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 2 - 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 && std::min(V0.size(), V1.size()) < 3)
	{
		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 op0 = -1, op1 = -1;
	while (Q < 82)
	{
		if (op0 == -1)
		{
			if (unused == n)
				return V0.size();
			if (unused == n - 1)
				return V0.size() + 1 - use_machine({ 0, n - 1 });
			if (unused == n - 2)
			{
				int r = use_machine({ V0[0], unused, V0[1], unused + 1 });
				return V0.size() + !(r & 2) + !(r & 1);
			}
			int r = use_machine({ V0[0], unused, V0[1], unused + 1, V0[2], unused + 2 });
			if (r & 1)
				V1.push_back(unused + 2);
			else
				V0.push_back(unused + 2);
			r >>= 1;
			if (r == 1)
			{
				op0 = unused;
				op1 = unused + 1;
			}
			else if (r == 0)
			{
				V0.push_back(unused);
				V0.push_back(unused + 1);
			}
			else
			{
				V1.push_back(unused);
				V1.push_back(unused + 1);
			}
			unused += 3;
		}
		else
		{
			if (unused == n)
				return V0.size() + 1;
			if (unused == n - 1)
				return V0.size() + 2 - use_machine({ 0, n - 1 });
			int r = use_machine({ unused, V0[0], unused + 1, V0[1], op0, V0[2], V1[0], op1, V1[1] }) - 1;
			if (r & 1)
				V1.push_back(unused);
			else
				V0.push_back(unused);
			if (r & 2)
				V1.push_back(unused + 1);
			else
				V0.push_back(unused + 1);
			if (r & 4)
			{
				V1.push_back(op0);
				V0.push_back(op1);
			}
			else
			{
				V0.push_back(op0);
				V1.push_back(op1);
			}
			op0 = op1 = -1;
			unused += 2;
		}
		Q++;
	}
	int O = V0.size() + (op0 != -1);
	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);
				unused += V0.size();
				if (r & 1)
					V1.push_back(unused - 1);
				else
					V0.push_back(unused - 1);
			}
			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(V1[i]);
					query.push_back(unused + i);
				}
				int r = use_machine(query);
				O += r + 1 >> 1;
				unused += V1.size();
				if (r & 1)
					V0.push_back(unused - 1);
				else
					V1.push_back(unused - 1);
			}
			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:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    if (n - unused > V0.size())
      |        ~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 0; i < V0.size(); i++)
      |                     ~~^~~~~~~~~~~
mushrooms.cpp:139:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |     O += V0.size() - (r + 1 >> 1);
      |                       ~~^~~
mushrooms.cpp:154:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  154 |     return O + L - (use_machine(query) + 1 >> 1);
      |                     ~~~~~~~~~~~~~~~~~~~^~~
mushrooms.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |    if (n - unused > V1.size())
      |        ~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for (int i = 0; i < V1.size(); i++)
      |                     ~~^~~~~~~~~~~
mushrooms.cpp:167:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |     O += r + 1 >> 1;
      |          ~~^~~
mushrooms.cpp:182:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  182 |     return O + (use_machine(query) + 1 >> 1);
      |                 ~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 100 / 100