Submission #772418

#	Time	Username	Problem	Language	Result	Execution time	Memory
772418		SanguineChameleon	Counting Mushrooms (IOI20_mushrooms)	C++17	10 / 100	188 ms	1124 KiB

mushrooms

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

const int maxn = 2e4 + 20;
const int lim = 1e9 + 20;
int order[maxn];
vector<int> group[maxn];
mt19937 gen(69420);

int count_mushrooms(int n) {
	for (int i = 0; i < n; i++) {
		order[i] = i;
	}
	shuffle(order + 1, order + n, gen);
	int pt = 1;
	group[0].push_back(0);
	int cur = 0;
	while (pt < n && (int)group[0].size() < lim && (int)group[1].size() < lim) {
		cur ^= use_machine({order[pt - 1], order[pt]});
		group[cur].push_back(order[pt]);
		pt++;
	}
	return group[0].size();
}

• Subtask 1: 10 / 100