Submission #560546

#	Time	Username	Problem	Language	Result	Execution time	Memory
560546		AlperenT	Counting Mushrooms (IOI20_mushrooms)	C++17	56.64 / 100	12 ms	464 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

const int K = 100;

int count_mushrooms(int n){
	int acnt = 0;

	vector<int> a, b;

	a.push_back(0);

	stack<int> rem;

	for(int i = n - 1; i >= 1; i--) rem.push(i);

	while(!rem.empty() && (a.size() < K && b.size() < K)){
		int ans = use_machine({0, rem.top()});

		if(ans){
			b.push_back(rem.top());
			rem.pop();
		}
		else{
			a.push_back(rem.top());
			rem.pop();
		}
	}

	while(!rem.empty()){
		if(a.size() > b.size()){
			vector<int> m;

			int cnt = 0;

			for(int i = 1; i < a.size(); i++){
				if(!rem.empty()){
					m.push_back(rem.top());
					rem.pop();
					cnt++;
				}
				m.push_back(a[i]);
			}

			int ans = use_machine(m);

			acnt += cnt - (ans + 1) / 2;
		}
		else{
			vector<int> m;

			int cnt = 0;

			for(int i = 1; i < b.size(); i++){
				if(!rem.empty()){
					m.push_back(rem.top());
					rem.pop();
					cnt++;
				}
				m.push_back(b[i]);
			}

			int ans = use_machine(m);

			acnt += (ans + 1) / 2;
		}
	}

	return a.size() + acnt;
}

Compilation message (stderr)

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

• Subtask 1: 56.6416 / 100