제출 #312991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312991		kobus	버섯 세기 (IOI20_mushrooms)	C++17	92.62 / 100	10 ms	640 KiB

mushrooms

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


int count_mushrooms(int n){
	vector<int> s[2]={{0},{}};
	int nn[2]={0,0};
	vector<int> ns;
	for(int i=1;i<n;i++)ns.pb(i);
	int k=85;
	while(ns.size()>0){
		if(k>0 && ns.size()>1 && max(s[0].size(),s[1].size())>1){
			k--;
			int a=ns[ns.size()-1];
			int b=ns[ns.size()-2];
			ns.pop_back();
			ns.pop_back();
			bool si=1;
			if(s[0].size()>s[1].size())si=0;
			vector<int> v={s[si][0],a,s[si][1],b};
			int x=use_machine(v);
			if(x%2)s[!si].pb(b);
			else s[si].pb(b);
			x=x/2;
			if(x%2)s[!si].pb(a);
			else s[si].pb(a);
		}
		else{
			bool si=1;
			if(s[0].size()>s[1].size())si=0;
			int tam=min(s[si].size(),ns.size());
			vector<int> v(2*tam);
			for(int i=0;i<tam;i++){
				v[2*i]=s[si][i];
			}
			for(int i=0;i<tam;i++){
				v[2*i+1]=ns[ns.size()-i-1];
			}
			for(int i=0;i<tam;i++)ns.pop_back();
			int x=use_machine(v);
			if(x%2)s[!si].pb(v[2*tam-1]);
			else s[si].pb(v[2*tam-1]);
			x=x/2;
			nn[!si]+=x;
			nn[si]+=tam-1-x;
		}
	}
	return s[0].size()+nn[0];
}

• Subtask 1: 92.623 / 100