Submission #833990

#	Time	Username	Problem	Language	Result	Execution time	Memory
833990		Johann	Counting Mushrooms (IOI20_mushrooms)	C++14	87.94 / 100	7 ms	388 KiB

mushrooms

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

typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int count_mushrooms(int n)
{
	vi m;
	// 0 for a and 1 for b
	vvi sure(2);
	vi cnt(2, 0);
	sure[0].push_back(0);
	cnt[0] = 1;
	int idx = 1;
	while (idx < n && max(sz(sure[0]), sz(sure[1])) < 2)
	{
		assert(sz(sure[0]) > 0);
		m.clear();
		m.push_back(sure[0].front());
		m.push_back(idx++);
		int c1 = use_machine(m);
		++cnt[c1], sure[c1].push_back(m.back());
	}
	while (idx < n && max(sz(sure[0]), sz(sure[1])) < sqrt(n) - 2)
	{
		int i = (sz(sure[0]) < sz(sure[1]));
		m.clear();
		for (int j = 0; j < 2; ++j)
		{
			m.push_back(sure[i][j]);
			if (idx < n)
				m.push_back(idx++);
		}
		int c2 = use_machine(m);
		++cnt[i ^ (c2 / 2)], sure[i ^ (c2 / 2)].push_back(m[1]);
		if (sz(m) > 3)
			++cnt[i ^ (c2 & 1)], sure[i ^ (c2 & 1)].push_back(m[3]);
	}

	while (idx < n)
	{
		int i = (sz(sure[0]) < sz(sure[1]));
		m.clear();
		for (int j = 0; j < sz(sure[i]) && idx < n; ++j)
		{
			m.push_back(sure[i][j]);
			m.push_back(idx++);
		}
		int c3 = use_machine(m);
		int lenCnt = (sz(m) - 2) / 2;
		cnt[i] += lenCnt - (c3 / 2);
		cnt[i ^ 1] += c3 / 2;

		++cnt[i ^ (c3 & 1)], sure[i ^ (c3 & 1)].push_back(m.back());
	}

	return cnt[0];
}

• Subtask 1: 87.9377 / 100