Submission #604935

#	Time	Username	Problem	Language	Result	Execution time	Memory
604935		Tigryonochekk	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	10 ms	308 KiB

mushrooms

#include <iostream>
#include "mushrooms.h"
#include <vector>
#define ll long long
using namespace std;

const int wtf = 200;

int count_mushrooms(int n) {
	vector<int> a, b;
	a.push_back(0);
	int ans = 1;
	int x = min(wtf, n);
	for (int i = 1; i < x; i++) {
		int u = use_machine({ 0, i });
		if (u == 0) {
			a.push_back(i);
			ans++;
		}
		else {
			b.push_back(i);
		}
	}
	if (x == n) 
		return ans;
	if (a.size() >= b.size()) {
		int c = a.size();
		int i = x;
		while (i + (c - 1) - 1 < n) {
			vector<int> m;
			m.push_back(a[0]);
			for (int j = 1; j < c; j++) {
				m.push_back(i);
				i++;
				m.push_back(a[j]);
			}
			if (m.size() >= 1) {
				int k = use_machine(m);
				ans += c - 1 - k / 2;
			}
		}
		vector<int> m;
		m.push_back(a[0]);
		int j = 1;
		for (; i < n; i++) {
			m.push_back(i);
			m.push_back(a[j]);
			j++;
		}
		if (m.size() >= 1) {
			int k = use_machine(m);
			ans += j - 1 - k / 2;
		}
	}
	else {
		int c = b.size();
		int i = x;
		while (i + (c - 1) - 1 < n) {
			vector<int> m;
			m.push_back(b[0]);
			for (int j = 1; j < c; j++) {
				m.push_back(i);
				i++;
				m.push_back(b[j]);
			}
			if (m.size() > 1) {
				int k = use_machine(m);
				ans += k / 2;
			}
		}
		vector<int> m;
		m.push_back(b[0]);
		int j = 1;
		for (; i < n; i++) {
			m.push_back(i);
			m.push_back(b[j]);
			j++;
		}
		if (m.size() >= 1) {
			int k = use_machine(m);
			ans += k / 2;
		}
	}
	return ans;
}

/*
8 
0 1 1 0 1 0 1 0

11 
0 1 1 1 1 1 1 0 0 0 0
*/

• Subtask 1: 0 / 100