Submission #304371

#	Time	Username	Problem	Language	Result	Execution time	Memory
304371		QAQAutoMaton	Counting Mushrooms (IOI20_mushrooms)	C++17	56.93 / 100	12 ms	384 KiB

mushrooms

#include "mushrooms.h"
#include<algorithm>
int solve(int n,std::vector<int> &a){
	std::vector<int> b;
	int st=200,ans=0;
	while(st<n){
		int m=std::min(n-st,(int)a.size());
		b.clear();
		for(int i=0;i<m;++i){
			b.emplace_back(st+i);
			b.emplace_back(a[i]);
		}
		ans+=(use_machine(b)+1)>>1;
		st+=m;
	}
	return ans;
}
int count_mushrooms(int n) {
	std::vector<int> A(0),B(0);
	A.emplace_back(0);
	for(int i=1;i<200 && i<n;++i){
		if(use_machine({0,i}))B.emplace_back(i);
		else A.emplace_back(i);
	}
	if(n<=200)return A.size();
	if(A.size()>B.size()){
		return A.size()+(n-200)-solve(n,A);	
	}
	else{
		return A.size()+solve(n,B);	
	}
}

• Subtask 1: 56.927 / 100