Submission #1186699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186699		hengliao	Counting Mushrooms (IOI20_mushrooms)	C++20	56.93 / 100	4 ms	680 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=100;

int count_mushrooms(int n) {
	ll cnt[2]={};
	ll ans[2]={};
	vll dumb(n-1);
	for(ll i=0;i<n-1;i++){
		dumb[i]=i+1;
	}
	shuffle(dumb.begin(), dumb.end(), rng);
	vll ord;
	ord.pb(0);
	for(auto &it:dumb){
		ord.pb(it);
	}
	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(ord[i]);
		ll re=use_machine(tep);
		cnt[re]++;
		ans[re]++;
		v[re].pb(ord[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(ord[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(ord[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.927 / 100