제출 #804764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
804764		alvingogo	버섯 세기 (IOI20_mushrooms)	C++14	90.40 / 100	8 ms	464 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<95;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: 90.4 / 100