Submission #304397

#	Time	Username	Problem	Language	Result	Execution time	Memory
304397		QAQAutoMaton	Counting Mushrooms (IOI20_mushrooms)	C++17	80.71 / 100	12 ms	396 KiB

mushrooms

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

		}
	}
	return ans;
}

• Subtask 1: 80.7143 / 100