Submission #828631

#	Time	Username	Problem	Language	Result	Execution time	Memory
828631		Minindu206	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	2 ms	336 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
	vector<int> posa, posb, pos;
	int acnt = 1, bcnt = 0, cnt, ans = 0;
	posa.push_back(0);
	for(int i=1;i<min(200, n);i++)
	{
		int cur = use_machine({0, i});
		if(cur == 0)
			posa.push_back(i), acnt++;
		else
			posb.push_back(i), bcnt++, ans++;
	}
	if(n <= 200)
	{
		return n - ans;
	}
	if(acnt >= bcnt)
		pos = posa, cnt = acnt;
	else
		pos = posb, cnt = bcnt;
	
	int i = 200;
	while(i < n)
	{
		vector<int> chk;
		int cur = 0;
		while(i < min(n, i + cnt))
		{
			chk.push_back(i);
			chk.push_back(pos[cur]);
			cur++;
			i++;
		}
		int ncur = use_machine(chk);
		if(acnt >= bcnt)
			ans += (ncur + 1) / 2;
		else
			ans += (cur - ((ncur + 1) / 2));
	}	
	return n - ans;
}

• Subtask 1: 0 / 100