Submission #304435

#	Time	Username	Problem	Language	Result	Execution time	Memory
304435		QAQAutoMaton	Counting Mushrooms (IOI20_mushrooms)	C++17	92.24 / 100	10 ms	384 KiB

mushrooms

#include "mushrooms.h"
#include<algorithm>
int min(int x,int y){return x<y?x:y;}
const int B=71;
int count_mushrooms(int n) {
	std::vector<int> xA({0}),xB(0),ask;
	if(n<=B){
		int ans=1;
		for(int i=1;i<n;++i){
			ans+=!use_machine({0,i});
		}
		return ans;
	}
	else{
		int x=!use_machine({0,1}),y=!use_machine({0,2});
		(x?xA:xB).emplace_back(1);
		(y?xA:xB).emplace_back(2);
		int s1,s2,w;
		if(x){s1=0,s2=1;w=0;}
		else if(y){s1=0;s2=2;w=0;}
		else{s1=1;s2=2;w=3;}
		if(n<=B+B+3){
			for(int i=3;i<n;i+=2){
				if(i+1==n){
					(!use_machine({0,i})?xA:xB).emplace_back(i);
				}
				else{
					int v=use_machine({s1,i,s2,i+1})^w;
					(v&2?xB:xA).emplace_back(i);
					(v&1?xB:xA).emplace_back(i+1);
				}
			}
			return xA.size();
		}
		else{
			for(int i=0;i<B;++i){
				int v=use_machine({s1,(i<<1)+3,s2,(i<<1)+4})^w;
				(v&2?xB:xA).emplace_back((i<<1)+3);
				(v&1?xB:xA).emplace_back((i<<1)+4);
			}
		}
	}
	int ans=xA.size();
	int at=B+B+3;
	while(at<n){
		ask.clear();
		if(xA.size()>xB.size()){
			int m=min(xA.size(),n-at);
			for(int i=0;i<m;++i){
				ask.emplace_back(at+i);
				ask.emplace_back(xA[i]);
			}
			int w=use_machine(ask);
			(w&1?xB:xA).emplace_back(at);
			ans+=m-((w+1)>>1);
			at+=m;
		}else{
			int m=min(xB.size(),n-at);
			for(int i=0;i<m;++i){
				ask.emplace_back(at+i);
				ask.emplace_back(xB[i]);
			}
			int w=use_machine(ask);
			(w&1?xA:xB).emplace_back(at);
			ans+=((w+1)>>1);
			at+=m;
		}
	}
	return ans;
}

• Subtask 1: 92.2449 / 100