Submission #377843

#	Time	Username	Problem	Language	Result	Execution time	Memory
377843		autumn_eel	Counting Mushrooms (IOI20_mushrooms)	C++14	56.50 / 100	29 ms	600 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) {
	vector<int>f(n);
	random_device rnd;
	rep(i,n)f[i]=i;
	shuffle(f.begin()+1,f.end(),rnd);
	
	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;
		}
	}
	if(n<=3)M=n;
	//~ cout<<Min<<' '<<M<<endl;
	vector<int>black,white;
	black.push_back(0);
	for(int i=1;i<M;i++){
		vector<int>v={0,f[i]};
		int c=use_machine(v);
		if(c==0)black.push_back(f[i]);
		else white.push_back(f[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(f[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: 56.5 / 100