Submission #804765

#	Time	Username	Problem	Language	Result	Execution time	Memory
804765		alvingogo	Counting Mushrooms (IOI20_mushrooms)	C++14	91.50 / 100	8 ms	448 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int count_mushrooms(int n) {
	if(n<=220){
		int ans=1;
		for(int i=1;i<n;i++){
			ans+=1-use_machine({0,i});
		}
		return ans;
	}
	int a=use_machine({0,1});
	int b=use_machine({0,2});
	vector<int> v[2];
	v[0].push_back(0);
	if(a){
		v[1].push_back(1);
	}
	else{
		v[0].push_back(1);
	}
	if(b){
		v[1].push_back(2);
	}
	else{
		v[0].push_back(2);
	}
	int r=3;
	for(;r<113;r+=2){
		int y=0;
		if(v[1].size()>=2){
			y=1;
		}
		int u34=use_machine({r,v[y][0],r+1,v[y][1]});
		if(u34%2==0){
			v[y].push_back(r);
		}
		else{
			v[y^1].push_back(r);
		}
		if(u34>=2){
			v[y^1].push_back(r+1);
		}
		else{
			v[y].push_back(r+1);
		}
	}
	int ans=0;
	while(r<n){
		int z=0;
		if(v[1].size()>v[0].size()){
			z=1;
		}
		int w=min(n,r+(int)v[z].size());
		vector<int> t;
		int s=0;
		for(int i=r;i<w;i++){
			t.push_back(i);
			t.push_back(v[z][i-r]);
			s++;
		}
		int u=use_machine(t);
		if(z==1){
			ans+=u/2;
		}
		else{
			ans+=s-(u/2)-1;
		}
		if(u%2==0){
			v[z].push_back(r);
		}
		else{
			v[z^1].push_back(r);
		}
		r=w;
	}
	ans+=v[0].size();
	return ans;
}

• Subtask 1: 91.498 / 100