Submission #1313604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313604		PlayVoltz	버섯 세기 (IOI20_mushrooms)	C++20	72.67 / 100	3 ms	428 KiB

mushrooms

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

const int X=90;

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

int count_mushrooms(int n){
	int p=1;
	vector<int> a(1, 0), b;
	while (a.size()<X&&b.size()<X&&p<n){
		if (a.size()>=2&&p+1<n){
			vector<int> temp;
			temp.pb(a[0]);
			temp.pb(p);
			++p;
			temp.pb(a[1]);
			temp.pb(p);
			++p;
			int res=use_machine(temp);
			if (res&1)b.pb(p-1);
			else a.pb(p-1);
			if (res&2)b.pb(p-2);
			else a.pb(p-2);
		}
		else if (b.size()>=2&&p+1<n){
			vector<int> temp;
			temp.pb(b[0]);
			temp.pb(p);
			++p;
			temp.pb(b[1]);
			temp.pb(p);
			++p;
			int res=use_machine(temp);
			if (res&1)a.pb(p-1);
			else b.pb(p-1);
			if (res&2)a.pb(p-2);
			else b.pb(p-2);
		}
		else{
			vector<int> temp;
			temp.pb(a[0]);
			temp.pb(p);
			int res=use_machine(temp);
			if (res)b.pb(p);
			else a.pb(p);
			++p;
		}
	}
	int ans=a.size();
	if (a.size()>=b.size()){
		while (p<n){
			vector<int> temp;
			for (int i=0; i<a.size()&&p<n; ++i)temp.pb(a[i]), temp.pb(p), ++p;
			int res=use_machine(temp);
			ans+=temp.size()/2-(res/2+res%2);
			if (res%2)b.pb(p-1);
		}
	}
	else{
		while (p<n){
			vector<int> temp;
			for (int i=0; i<b.size()&&p<n; ++i)temp.pb(b[i]), temp.pb(p), ++p;
			int res=use_machine(temp);
			ans+=res/2+res%2;
			if (res%2)a.pb(p-1);
		}
	}
	return ans;
}

• Subtask 1: 72.6688 / 100