Submission #530015

#	Time	Username	Problem	Language	Result	Execution time	Memory
530015		jamezzz	Counting Mushrooms (IOI20_mushrooms)	C++17	89.33 / 100	10 ms	456 KiB

mushrooms

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

#define pf printf
#define pb push_back
#define sz(x) (int)x.size()

int k=40;

int count_mushrooms(int n){
	vector<int> a,b,v;
	a.pb(0);
	for(int i=1;i<n;++i)v.pb(i);
	int na=1;
	while(!v.empty()){
		vector<int> g;
		if(sz(a)>=sz(b)){
			int x=sz(a);
			if(2<=x&&x<=k)x=2;
			for(int i=0;i<x;++i){
				if(v.empty())break;
				g.pb(a[i]);
				g.pb(v.back());
				v.pop_back();
			}
			int res=use_machine(g);
			na+=sz(g)/2-(res+1)/2;
			if(res%2)b.pb(g.back());
			else a.pb(g.back());
			if(x==2){
				if(res>=2)b.pb(g[1]);
				else a.pb(g[1]);
			}
		}
		else{
			int x=sz(b);
			if(2<=x&&x<=k)x=2;
			for(int i=0;i<x;++i){
				if(v.empty())break;
				g.pb(b[i]);
				g.pb(v.back());
				v.pop_back();
			}
			int res=use_machine(g);
			na+=(res+1)/2;
			if(res%2)a.pb(g.back());
			else b.pb(g.back());
			if(x==2){
				if(res>=2)a.pb(g[1]);
				else b.pb(g[1]);
			}
		}
	}
	return na;
}

• Subtask 1: 89.3281 / 100