Submission #772434

#	Time	Username	Problem	Language	Result	Execution time	Memory
772434		SanguineChameleon	Counting Mushrooms (IOI20_mushrooms)	C++17	56.93 / 100	9 ms	976 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);
	int cur = 0;
	while (pt < n && (int)group[0].size() < lim && (int)group[1].size() < lim) {
		type[order[pt]] = type[order[pt - 1]] ^ use_machine({order[pt - 1], 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;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:20:6: warning: unused variable 'cur' [-Wunused-variable]
   20 |  int cur = 0;
      |      ^~~

• Subtask 1: 56.927 / 100