Submission #1023011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023011		TheWilp	Counting Mushrooms (IOI20_mushrooms)	C++14	92.62 / 100	6 ms	600 KiB

mushrooms

#include "mushrooms.h"

int count_mushrooms(int n) {
	if(n == 1) return 1;
	std::vector<int> A;
	std::vector<int> B;
	A.push_back(0);
	int ans = 0;

	int i = 1;
	while(i < n) {
		bool Abase = B.size() <= A.size();
		std::vector<int>* in = Abase ? &A : &B;
		std::vector<int> v;

		if(in->size() >= 2 && in->size() < 80) {
			v.push_back((*in)[0]);
			v.push_back(i++);
			v.push_back((*in)[1]);
			bool back_push = i < n;
			if(back_push) v.push_back(i++);

			int count = use_machine(v);
			if(Abase) {
				if(back_push) {
					if(count%2) B.push_back(v.back());
					else A.push_back(v.back());
				}
				if(count > 1) B.push_back(v[1]);
				else A.push_back(v[1]);
			}
			else {
				if(back_push) {
					if(count%2) A.push_back(v.back());
					else B.push_back(v.back());
				}
				if(count > 1) A.push_back(v[1]);
				else B.push_back(v[1]);
			}
		}
		else {
			int c = 1;
			v.push_back((*in)[0]);
			while(i < n) {
				if(c < in->size()) {
					v.push_back(i++);
					v.push_back((*in)[c++]);
				}
				else {
					break;
				}
			}
			bool pos_push = false;
			if(i < n) v.push_back(i++),pos_push = true;
			int count = use_machine(v);
			if(Abase) {
				ans += (v.size() + 1) / 2 - 1 - count / 2;
				if(pos_push) 
					if(count%2) B.push_back(v.back());
					else A.push_back(v.back());
			}
			else {
				ans += count / 2;
				if(pos_push) 
					if(count%2) A.push_back(v.back());
					else B.push_back(v.back());
			}
		}
	}
	return ans + A.size();
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:45:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     if(c < in->size()) {
      |        ~~^~~~~~~~~~~~
mushrooms.cpp:58:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   58 |     if(pos_push)
      |       ^
mushrooms.cpp:64:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   64 |     if(pos_push)
      |       ^

• Subtask 1: 92.623 / 100