Submission #606570

#	Time	Username	Problem	Language	Result	Execution time	Memory
606570		CyberCow	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	12 ms	376 KiB

mushrooms

#include "mushrooms.h"
#include <vector>
using namespace std;
vector<int> a, b;

int count_mushrooms(int n) {
	int ans = 1, gt = 0;
	if (n <= 250)
	{
		for (int i = 1; i < n - 1; i += 2)
		{
			ans += 2 - use_machine({ i, 0, i + 1 });
		}
		if (n % 2 == 0)
			ans += 1 - use_machine({ 0, n - 1 });
		return ans;
	}
	int st = 0, st1 = 0;
	a.push_back(0);
	if (use_machine({ 0, 1 }))
	{
		st = 1;
		b.push_back(1);
		if (use_machine({ 0, 2 }))
		{
			st1 = 1;
			b.push_back(2);
		}
		else
		{
			a.push_back(2);
		}
	}
	else
	{
		a.push_back(1);
		if (use_machine({ 0, 2 }))
		{
			st1 = 1;
			b.push_back(2);
		}
		else
		{
			a.push_back(2);
		}
	}
	if (st == 0)
	{
		for (int i = 3; i < 160; i += 2)
		{
			int qan = use_machine({ 0, i, 1, i + 1 });
			if (qan == 0)
			{
				a.push_back(i);
				a.push_back(i + 1);
			}
			else if (qan == 1)
			{
				a.push_back(i);
				b.push_back(i + 1);
			}
			else if (qan == 2)
			{
				b.push_back(i);
				a.push_back(i + 1);
			}
			else
			{
				b.push_back(i);
				b.push_back(i + 1);
			}
		}
	}
	else if (st == 1 && st1 == 0)
	{
		for (int i = 3; i < 160; i += 2)
		{
			int qan = use_machine({ 0, i, 2, i + 1 });
			if (qan == 0)
			{
				a.push_back(i);
				a.push_back(i + 1);
			}
			else if (qan == 1)
			{
				a.push_back(i);
				b.push_back(i + 1);
			}
			else if (qan == 2)
			{
				b.push_back(i);
				a.push_back(i + 1);
			}
			else
			{
				b.push_back(i);
				b.push_back(i + 1);
			}
		}
	}
	else
	{
		for (int i = 3; i < 160; i += 2)
		{
			int qan = use_machine({ 1, i, 2, i + 1 });
			if (qan == 0)
			{
				b.push_back(i);
				b.push_back(i + 1);
			}
			else if (qan == 1)
			{
				b.push_back(i);
				a.push_back(i + 1);
			}
			else if (qan == 2)
			{
				a.push_back(i);
				b.push_back(i + 1);
			}
			else
			{
				a.push_back(i);
				a.push_back(i + 1);
			}
		}
	}
	ans = a.size();
	int j;
	vector<int> x;
	for (int i = 161; i < n; i++)
	{
		x.clear();
		if (a.size() > b.size())
		{
			int vr = 0;
			for (j = 0; j < a.size() && i + j < n; j++)
			{
				x.push_back(a[j]);
				x.push_back(i + j);
				vr = j;
			}
			int f = use_machine(x);
			ans += vr - f / 2;
			if (f % 2)
			{
				b.push_back(x[x.size() - 1]);
			}
			else
			{
				a.push_back(x[x.size() - 1]);
				ans++;
			}
			i += vr;
		}
		else
		{
			int vr = 0;
			for (j = 0; j < b.size() && i + j < n; j++)
			{
				x.push_back(b[j]);
				x.push_back(i + j);
				vr = j;
			}
			int f = use_machine(x);
			ans += f / 2;
			if (f % 2)
			{
				a.push_back(x[x.size() - 1]);
				ans++;
			}
			else
			{
				b.push_back(x[x.size() - 1]);
			}
			i += vr;
		}
	}
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:137:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    for (j = 0; j < a.size() && i + j < n; j++)
      |                ~~^~~~~~~~~~
mushrooms.cpp:159:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |    for (j = 0; j < b.size() && i + j < n; j++)
      |                ~~^~~~~~~~~~
mushrooms.cpp:7:15: warning: unused variable 'gt' [-Wunused-variable]
    7 |  int ans = 1, gt = 0;
      |               ^~

• Subtask 1: 92.623 / 100