제출 #377794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377794		autumn_eel	버섯 세기 (IOI20_mushrooms)	C++14	0 / 100	0 ms	364 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;

int count_mushrooms(int n) {
	int Min=INT_MAX;
	int M=-1;
	for(int N=1;N<=n;N++){
		int c=N+2*(n-N)/N;
		if(Min>c){
			M=N;
			Min=c;
		}
	}
	//~ cout<<Min<<' '<<M<<endl;
	vector<int>black,white;
	black.push_back(0);
	for(int i=1;i<M;i++){
		vector<int>v={0,i};
		int c=use_machine(v);
		if(c==0)black.push_back(i);
		else white.push_back(i);
	}
	vector<int>idx=(black.size()>white.size()?black:white);

	int ans=0;
	
	int rest=n-M;
	int cur=M;
	while(rest){
		int d=min(rest,(int)idx.size()-1);
		vector<int>v;
		rep(i,d){
			v.push_back(idx[i]);
			v.push_back(cur+i);
		}
		v.push_back(idx.back());
		int c=use_machine(v);
		assert(c%2==0);
		ans+=c/2;
		cur+=d;
		rest-=d;
	}

	if(black.size()>white.size()){
		return n-(white.size()+ans);
	}
	else{
		return black.size()+ans;
	}
}

• Subtask 1: 0 / 100