Submission #604867

#	Time	Username	Problem	Language	Result	Execution time	Memory
604867		CyberCow	Counting Mushrooms (IOI20_mushrooms)	C++17	55.66 / 100	12 ms	336 KiB

mushrooms

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

int count_mushrooms(int n) {
	a.push_back(0);
	int ans = 1, gt = 0;
	for (int i = 1; i < min(170, n); i++)
	{
		if (use_machine({ 0, i }) == 1)
		{
			b.push_back(i);
			nsh[i] = 1;
		}
		else
		{
			a.push_back(i);
			nsh[1] = 0;
			ans++;
		}
	}
	if (n <= 170)
		return ans;
	int qan = 0, atb = 0, aq = 0, bq = 0, anc = 169;
	if (a.size() < b.size())
		atb = 1;
	vector<int> x;
	for (int i = 170; i < n; i++)
	{
		if (atb == 0)
		{
			x.push_back(a[aq]);
			aq++;
			x.push_back(i);
			if (aq == a.size() - 1 || i == n - 1)
			{
				x.push_back(a[aq]);
				ans += (2 * (i - anc) - use_machine(x)) / 2;
				x.clear();
				aq = 0;
				anc = i;
			}
		}
		else
		{
			x.push_back(b[bq]);
			bq++;
			x.push_back(i);
			if (bq == b.size() - 1 || i == n - 1)
			{
				x.push_back(b[bq]);
				ans += use_machine(x) / 2;
				x.clear();
				bq = 0;
				anc = i;
			}
		}
	}
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    if (aq == a.size() - 1 || i == n - 1)
      |        ~~~^~~~~~~~~~~~~~~
mushrooms.cpp:51:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    if (bq == b.size() - 1 || i == n - 1)
      |        ~~~^~~~~~~~~~~~~~~
mushrooms.cpp:9:15: warning: unused variable 'gt' [-Wunused-variable]
    9 |  int ans = 1, gt = 0;
      |               ^~
mushrooms.cpp:26:6: warning: unused variable 'qan' [-Wunused-variable]
   26 |  int qan = 0, atb = 0, aq = 0, bq = 0, anc = 169;
      |      ^~~

• Subtask 1: 55.665 / 100