Submission #1206136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206136		tkm_algorithms	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	0 ms	320 KiB

mushrooms

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long

const char nl = '\n';

int count_mushrooms(int n) {
	int k = 25*(sqrt(n*8)-1)/100;
	vector<int> a(1), b;
	int res = 1, start = 0;
	for (int i = 1; i <= min(n-1, 2*k-1); ++i) {
		vector<int> x = {0, i};
		int cnt = use_machine(x);
		if (cnt == 0){a.push_back(i); res += 1;}
		else b.push_back(i);
		if (sz(a) == k || sz(b) == k) {
			start = i+1;
			break;
		}	
	}
	
	if (sz(a) < k && sz(b) < k)return res;
	
	bool ok = false;
	if (sz(b) == k)swap(a, b), ok = true;
	
	while (start < n) {
		int mn = min(n-start, k);
		vector<int> x;
		for (int i = 0; i < mn; ++i) {
			x.push_back(i+start);
			x.push_back(a[i]);
		}
		int cnt = use_machine(x);
		cnt = (cnt+1)/2;
		if (ok)cnt = mn-cnt;
		res += cnt;
		start += k;
	}
	return res;
}

//int main() {
//}

• Subtask 1: 0 / 100