Submission #390591

#	Time	Username	Problem	Language	Result	Execution time	Memory
390591		AdOjis485	Counting Mushrooms (IOI20_mushrooms)	C++17	56.64 / 100	13 ms	392 KiB

mushrooms

#include "mushrooms.h"
#include <iostream>
using namespace std;

int count_mushrooms(int n)
{

	if(n < 6)
	{
		int count = 1;
		for(int i = 1; i < n; i ++)
		{
			count += 1 - use_machine({0, i});
		}
		return count;
	}

	vector<int> type(n, -1);
	vector<int> a = {0};
	vector<int> b;
	type[0] = 0;

	int sqrt;
	for(int i = 1; i * i < 2 * n; i ++)
	{
		sqrt = i;
		type[i] = use_machine({0, i});
		if(type[i] == 0) a.push_back(i);
		else b.push_back(i);
	}

	int ans = a.size();
	bool typea = true;
	if(b.size() > a.size())
	{
		a = b;
		typea = false;
	}
	int n2 = a.size();
	vector<int> c(2 * n2 - 1);
	for(int i = 0; i < a.size(); i ++) c[2 * i] = a[i];

	int j = sqrt + 1;
	while(j < n)
	{
		for(int i = 1; i < n2; i ++, j ++)
		{
			if(j >= n)
			{
				c.pop_back();
				c.pop_back();
			} 
			else c[2 * i - 1] = j;
		}
		//for(auto el : c) cerr << el << " ";
		//cerr << ' ';
		if(c.size() == 1) break;
		if(typea) ans += (c.size() - use_machine(c)) / 2;
		else ans += use_machine(c) / 2;
		//cerr << ans << '\n';

	}
	
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < a.size(); i ++) c[2 * i] = a[i];
      |                 ~~^~~~~~~~~~

• Subtask 1: 56.6416 / 100