Submission #772607

#	Time	Username	Problem	Language	Result	Execution time	Memory
772607		SanguineChameleon	Counting Mushrooms (IOI20_mushrooms)	C++17	70.85 / 100	8 ms	920 KiB

mushrooms

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

const int maxn = 2e4 + 20;
const int lim = 80;
vector<int> type[maxn];
int n, res, pt;

void alternate(int k) {
	k = min(min(k, n - pt), max((int)type[0].size(), (int)type[1].size()));
	if (k == 0) {
		return;
	}
	int t = (int)type[0].size() >= k ? 0 : 1;
	vector<int> q;
	for (int i = 0; i < k; i++) {
		q.push_back(type[t][i]);
		q.push_back(pt + i);
	}
	int cnt = use_machine(q);
	if (t == 0) {
		res += k - (cnt + 1) / 2;
	}
	else {
		res += (cnt + 1) / 2;
	}
	type[t ^ (cnt & 1)].push_back(pt + k - 1);
	if ((cnt >> 1) == (k - 1)) {
		for (int i = 0; i < k - 1; i++) {
			type[t ^ 1].push_back(pt + i);
		}
	}
	else if ((cnt >> 1) == 0) {
		for (int i = 0; i < k - 1; i++) {
			type[t].push_back(pt + i);
		}
	}
	else if (k == 3 && pt + 5 <= n) {
		if ((int)type[t ^ 1].size() < 2) {
			alternate(2);
			res -= 1;
			pt -= 2;
		}
		else {
/*			cnt = use_machine({type[t ^ 1][0], pt, type[t ^ 1][1], type[t][0], pt + 1, type[t][1], pt + 3, type[t][2], pt + 4}) - 1;
			type[t ^ (cnt & 1)].push_back(pt + 4);
			type[t ^ (cnt & 2)].push_back(pt + 3);
			type[t ^ 1 ^ (cnt & 4)].push_back(pt);
			type[t ^ (cnt & 4)].push_back(pt + 1);
			pt += 2;*/
		}
	}
	pt += k;
}

int count_mushrooms(int _n) {
	n = _n;
	type[0].push_back(0);
	res = 1;
	pt = 1;
	alternate(1);
	alternate(1);
	alternate(2);
	while (pt < n && (int)type[0].size() < lim && (int)type[1].size() < lim) {
		alternate(3);
	}
	while (pt < n) {
		alternate(n);
	}
	return res;
}

• Subtask 1: 70.8464 / 100