Submission #622771

#	Time	Username	Problem	Language	Result	Execution time	Memory
622771		erekle	Counting Mushrooms (IOI20_mushrooms)	C++17	87.60 / 100	17 ms	336 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

int count_mushrooms(int n) {
	int s = 141; // sqrt(20000)
	// ADD RANDOM_SHUFFLE LATER
	
	// find first 2s values pairwise
	vector<int> id[2]; // A, B
	id[0].push_back(0);
	vector<int> m;
	int last = min(2*s, n);
	for (int i = 1; i < last; ) {
		if (i+1 < last && (id[0].size() >= 2 || id[1].size() >= 2)) {
			int same = 0;
			if (id[0].size() < 2) same = 1;

			m = {id[same][0], i, id[same][1], i+1};
			int x = use_machine(m);
			if (x & 1) id[1-same].push_back(i+1);
			else id[same].push_back(i+1);
			if (x & 2) id[1-same].push_back(i);
			else id[same].push_back(i);
			i += 2;
		} else {
			m = {0, i};
			if (use_machine(m)) id[1].push_back(i);
			else id[0].push_back(i);
			i++;
		}
	}

	// find the rest of the values as blocks of s
	int A = id[0].size();
	for (int i = last; i < n; ) {
		int big = (id[1].size() > id[0].size() ? 1 : 0);
		int cnt = min((int)id[big].size(), n-i);
		m.clear();
		for (int j = 0; j < cnt; ++j) {
			m.push_back(i+j);
			m.push_back(id[big][j]);
		}
		int x = use_machine(m);
		if (x & 1) {
			id[1-big].push_back(i);
			++x;
		} else id[big].push_back(i);
		x /= 2;
		if (big == 0) x = cnt-x;
		A += x;
		i += cnt;
	}
	return A;
}

• Subtask 1: 87.5969 / 100