Submission #433936

#	Time	Username	Problem	Language	Result	Execution time	Memory
433936		kwongweng	Counting Mushrooms (IOI20_mushrooms)	C++17	56.78 / 100	19 ms	304 KiB

mushrooms

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

int count_mushrooms(int n) {
	vector<int> m;
	int ans = 1;
	vector<int> a, b;
	a.push_back(0);
	for (int i = 1; i < min(n, 201); i++){
		m = {0, i};
		int cnt = use_machine(m);
		if (cnt == 0){
			ans++;
			a.pb(i);
		}else{
			b.pb(i);
		}
	}
	int A = a.size();
	int B = b.size();
	if (A >= B){
		for (int i = 201; i < n; i += A-1){
			int len = min(A-1, n-i);
			m = {a[0]};
			for (int j = 0; j < len; j++){
				m.pb(i+j);
				m.pb(a[j+1]);
			}
			ans += len - use_machine(m)/2;
		}
	}else{
		for (int i = 201; i < n; i += B-1){
			int len = min(B-1, n-i);
			m = {b[0]};
			for (int j = 0; j < len; j++){
				m.pb(i+j);
				m.pb(b[j+1]);
			}
			ans += use_machine(m)/2;
		}
	}
	return ans;
}

• Subtask 1: 56.7839 / 100