Submission #772436

#	Time	Username	Problem	Language	Result	Execution time	Memory
772436		SanguineChameleon	Counting Mushrooms (IOI20_mushrooms)	C++17	56.93 / 100	9 ms	940 KiB

mushrooms

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

const int maxn = 2e4 + 20;
const int lim = 94;
int order[maxn];
int type[maxn];
vector<int> group[maxn];
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

int count_mushrooms(int n) {
	for (int i = 0; i < n; i++) {
		order[i] = i;
	}
	shuffle(order + 1, order + n, gen);
	int pt = 1;
	type[0] = 0;
	group[0].push_back(0);
	while (pt < n && (int)group[0].size() < lim && (int)group[1].size() < lim) {
		uniform_int_distribution<int> dist(0, pt - 1);
		int prv = dist(gen);
		type[order[pt]] = type[order[prv]] ^ use_machine({order[prv], order[pt]});
		group[type[order[pt]]].push_back(order[pt]);
		pt++;
	}
	int g = (int)group[0].size() >= lim ? 0 : 1;
	int res = (int)group[0].size();
	for (; pt < n;) {
		int k = min((int)group[g].size(), n - pt);
		vector<int> a;
		for (int i = 0; i < k; i++) {
			a.push_back(group[g][i]);
			a.push_back(order[pt + i]);
		}
		if (g == 0) {
			res += k - (use_machine(a) + 1) / 2;
		}
		else {
			res += (use_machine(a) + 1) / 2;
		}
		pt += k;
	}
	return res;
}

• Subtask 1: 56.927 / 100