Submission #838482

#	Time	Username	Problem	Language	Result	Execution time	Memory
838482		caganyanmaz	Counting Mushrooms (IOI20_mushrooms)	C++17	80.43 / 100	7 ms	332 KiB

mushrooms

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "mushrooms.h"

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int BLOCK = 140;

int count_mushrooms(int n) 
{
	vector<int> s[2]; // 0 - a, 1 - b
	s[0].pb(0);
	int i = 1;
	while (max(s[0].size(), s[1].size()) < 2 && i < n)
	{
		vector<int> v = {0, i};
		debug(v, "a");
		if (use_machine(v) == 1)
			s[1].pb(i);
		else
			s[0].pb(i);
		i++;
	}
	int current = 0;
	if (s[0].size() < 2)
		current = 1;

	int j = i+1;
	while (max(s[0].size(), s[1].size()) < BLOCK && j < n)
	{
		vector<int> v = {s[current][0], i, s[current][1], j};
		debug(v, "b");
		int res = use_machine(v);
		if (res&1)
			s[current^1].pb(j);
		else
			s[current].pb(j);
		if (res&2)
			s[current^1].pb(i);
		else
			s[current].pb(i);
		i+=2,j+=2;
	}
	if (s[0].size() >= s[1].size())
		current = 0;
	else
		current = 1;
	int counter = 0;
	while (i < n)
	{
		vector<int> v;
		for (int j = 0; j < s[current].size() && i < n; j++)
		{
			v.pb(s[current][j]);
			v.pb(i++);
		}
		debug(v, "c");
		counter += (use_machine(v) + 1) / 2;
	}
	if (current == 0)
		return n - counter - s[1].size();
	return s[0].size() + counter;

}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int j = 0; j < s[current].size() && i < n; j++)
      |                   ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 80.427 / 100