Submission #1312294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312294		LaMatematica14	Counting Mushrooms (IOI20_mushrooms)	C++20	84.01 / 100	4 ms	432 KiB

mushrooms

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


int count_mushrooms(int n) {
	vector<bool> m(n, 0);
	m[1] = use_machine({0, 1});
	if (n == 2) return m[1] ? 1 : 2; 

	m[2] = use_machine({0,2});

	int nx = 3;
	vector<int> a = {0}, b;
	if (m[1]) b.push_back(1);
	else a.push_back(1);
	if (m[2]) b.push_back(2);
	else a.push_back(2);

	auto first = [&](array<int, 2> t) {
		while (nx+1 < n && max(a.size(), b.size()) < block) {
			int q = use_machine({t[0], nx, t[1], nx+1});
			if (q < 2) m[nx] = m[t[0]]; 
			else  m[nx] = !m[t[0]];
			if ((q&1) == 1) m[nx+1] = !m[t[0]];
			else m[nx+1] = m[t[0]];

			if (m[nx]) b.push_back(nx);
			else a.push_back(nx);
			if (m[nx+1]) b.push_back(nx+1);
			else a.push_back(nx+1);

			nx += 2;
		}
	};
	
	if (a.size() > 1) first({a[0], a[1]});
	else first({b[0], b[1]});

	long long tota = a.size();

	auto second = [&](vector<int> &ts) {
		vector<int> query;
		for (int i = 0; i < ts.size() && i+nx < n; i++) {
			query.push_back(ts[i]);
			query.push_back(nx+i);
		}
		int hm = use_machine(query);
		nx += ts.size();
		tota += (m[ts[0]] ? (hm+1)/2 : query.size()/2 - (hm+1)/2);

		if ((hm&1) == 1) {
			if (m[ts[0]]) a.push_back(query.back());
			else b.push_back(query.back());
		}
	};

	while (nx < n) {
		if (a.size() > b.size()) second(a);
		else second(b);
	}

	return tota;
}

• Subtask 1: 84.0149 / 100