제출 #1186701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186701		hengliao	Counting Mushrooms (IOI20_mushrooms)	C++20	56.78 / 100	3 ms	432 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define vll vector<ll>
#define pll pair<ll, ll>
#define pb push_back

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef int ll;

const ll B=98;

int count_mushrooms(int n) {
	ll cnt[2]={};
	ll ans[2]={};
	array<vll, 2> v;
	v[0].pb(0);
	cnt[0]++;
	ans[0]++;
	for(ll i=1;i<n && i<2*B;i++){
		vll tep;
		tep.pb(0);
		tep.pb(i);
		ll re=use_machine(tep);
		cnt[re]++;
		ans[re]++;
		v[re].pb(i);
	}
	if(2*B>=n){
		return cnt[0];
	}
	if(cnt[0]>=cnt[1]){
		ll pt=2*B;
		while(pt<n){
			vll tep;
			ll cur=0;
			for(ll rep=0;rep<cnt[0];rep++){
				tep.pb(v[0][rep]);
				if(pt<n){
					tep.pb(pt);
					pt++;
					cur++;
				}
			}
			ll re=use_machine(tep);
			ll tep2=(re+1)/2;
			ans[1]+=tep2;
			ans[0]+=cur-tep2;
		}
		return ans[0];
	}	
	else{
		ll pt=2*B;
		while(pt<n){
			vll tep;
			ll cur=0;
			for(ll rep=0;rep<cnt[1];rep++){
				tep.pb(v[1][rep]);
				if(pt<n){
					tep.pb(pt);
					pt++;
					cur++;
				}
			}
			ll re=use_machine(tep);
			ll tep2=(re+1)/2;
			ans[0]+=tep2;
			ans[1]+=cur-tep2;
		}
		return ans[0];
	}
}

• Subtask 1: 56.7839 / 100