Submission #421439

#	Time	Username	Problem	Language	Result	Execution time	Memory
421439		Trunkty	Counting Mushrooms (IOI20_mushrooms)	C++14	79.86 / 100	17 ms	308 KiB

mushrooms

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

int count_mushrooms(int n){
	int nextm=1;
	vector<int> a = {0};
	vector<int> b = {};
	while(a.size()<3 and b.size()<3){
		if(nextm==n){
			break;
		}
		int x = use_machine({0,nextm});
		if(x==1){
			b.push_back(nextm);
		}
		else{
			a.push_back(nextm);
		}
		nextm++;
	}
	while(a.size()<141 and b.size()<141){
		if(nextm==n){
			break;
		}
		if(nextm==n-1){
			int x = use_machine({0,nextm});
			if(x==1){
				b.push_back(nextm);
			}
			else{
				a.push_back(nextm);
			}
			nextm++;
			break;
		}
		if(a.size()>=3){
			int x = use_machine({a[0],nextm,a[1],a[2],nextm+1});
			if(x==0){
				a.push_back(nextm);
				a.push_back(nextm+1);
			}
			else if(x==1){
				a.push_back(nextm);
				b.push_back(nextm+1);
			}
			else if(x==2){
				b.push_back(nextm);
				a.push_back(nextm+1);
			}
			else{
				b.push_back(nextm);
				b.push_back(nextm+1);
			}
			nextm+=2;
		}
		else{
			int x = use_machine({b[0],nextm,b[1],b[2],nextm+1});
			if(x==0){
				b.push_back(nextm);
				b.push_back(nextm+1);
			}
			else if(x==1){
				b.push_back(nextm);
				a.push_back(nextm+1);
			}
			else if(x==2){
				a.push_back(nextm);
				b.push_back(nextm+1);
			}
			else{
				a.push_back(nextm);
				a.push_back(nextm+1);
			}
			nextm+=2;
		}
	}
	int cnt=a.size();
	while(nextm<n){
		if(a.size()>=141){
			vector<int> mach = {a[0]};
			for(int i=1;i<a.size();i++){
				if(nextm==n){
					break;
				}
				mach.push_back(nextm);
				mach.push_back(a[i]);
				nextm++;
			}
			int x = use_machine(mach);
			cnt += ((mach.size()-1)/2)-x/2;
		}
		else{
			vector<int> mach = {b[0]};
			for(int i=1;i<b.size();i++){
				if(nextm==n){
					break;
				}
				mach.push_back(nextm);
				mach.push_back(b[i]);
				nextm++;
			}
			int x = use_machine(mach);
			cnt += x/2;
		}
	}
	return cnt;
}

Compilation message (stderr)

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

• Subtask 1: 79.8587 / 100