Submission #390566

#	Time	Username	Problem	Language	Result	Execution time	Memory
390566		AdOjis485	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	1 ms	200 KiB

mushrooms

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

int count_mushrooms(int n)
{
	vector<int> type(n, -1);
	vector<int> a = {0};
	vector<int> b;
	type[0] = 0;
	
	int sqrt;
	for(int i = 1; i * i < 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(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:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < a.size(); i ++) c[2 * i] = a[i];
      |                 ~~^~~~~~~~~~
mushrooms.cpp:32:6: warning: 'sqrt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |  int j = sqrt + 1;
      |      ^

• Subtask 1: 0 / 100