Submission #1294442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294442		m_bezrutchka	Counting Mushrooms (IOI20_mushrooms)	C++20	80.43 / 100	4 ms	436 KiB

mushrooms

// 80 points, q = 281
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

// obs nova: a ideia de alternar do codigo pra 57 eh particularmente
// util quando k = 2:
// fazer a query [x A y A] ou [x B y B]
// me diz exatamente os valores de x e y:
//  A A A A -> 0
//  A A B A -> 2
//  B A A A -> 1
//  B A B A -> 3
// e para B
//  A B A B -> 3
//  A B B B -> 1
//  B B A B -> 2
//  B B B B -> 0

// passo 1:
// 	2 queries pra saber 2 do mesmo tipo
// 	agora k - 2 queries pra saber k do mesmo tipo
// 	total: k queries
//
// passo 2:
//  igual antes, (n - 2k + 1) / k queries
//

// agora minimizing k + (n - 2k + 1) / k
//       minimizing k + n/k - 2
//			 minimizing k + n/k
// k = sqrt(n)
//
// k = 141
// 141 queries para descobrir 141 iguais entre os 281 primeiros
// agora sobraram (20000 - 281) / 141 ~ 140 queries pro resto
// 141 + 140 = 281 queries

int count_mushrooms(int n) {
	if (n == 1) return 1;

	vector<int> pos_A;
	vector<int> pos_B;

	pos_A.push_back(0);

	if (use_machine({0, 1}) == 0) pos_A.push_back(1);
	else pos_B.push_back(1);

	if (n == 2) return ((int) pos_A.size());

	if (use_machine({0, 2}) == 0) pos_A.push_back(2);
	else pos_B.push_back(2);

	int k = 141;

	// passo 1
	for (int i = 3; i < 2 * k - 1; i += 2) {
		if (i == n) return ((int) pos_A.size());
		if (i == n - 1) {
			return ((int) pos_A.size()) + (1 - use_machine({0, i}));
		}

		if ((int) pos_A.size() >= 2) {
			int ret = use_machine({i, pos_A[0], i+1, pos_A[1]});
			if (ret == 0) {
				pos_A.push_back(i);
				pos_A.push_back(i+1);
			} else if (ret == 1) {
				pos_B.push_back(i);
				pos_A.push_back(i+1);
			} else if (ret == 2) {
				pos_A.push_back(i);
				pos_B.push_back(i+1);
			} else {
				pos_B.push_back(i);
				pos_B.push_back(i+1);
			}
		} else {
			int ret = use_machine({i, pos_B[0], i+1, pos_B[1]});
			if (ret == 3) {
				pos_A.push_back(i);
				pos_A.push_back(i+1);
			} else if (ret == 2) {
				pos_B.push_back(i);
				pos_A.push_back(i+1);
			} else if (ret == 1) {
				pos_A.push_back(i);
				pos_B.push_back(i+1);
			} else {
				pos_B.push_back(i);
				pos_B.push_back(i+1);
			}
		}
	}

	int step = pos_A.size();
	bool using_b = false;
	if (pos_A.size() < pos_B.size()) {
		using_b = true;
		step = pos_B.size();
	}

	// cout << "pos_A: ";
	// for (int x: pos_A) {
	// 	cout << x << " ";
	// }
	// cout << endl;
	// cout << "pos_B: ";
	// for (int x: pos_B) {
	// 	cout << x << " ";
	// }
	// cout << endl;
	// cout << "using_b = " << using_b << endl;
	// cout << "step = " << step << endl;

	int ans = pos_A.size();
	int ini = 2 * k - 1;
	while (ini < n) {
		// ini x0 ini+1 x1 ini+2 x2 ... ini+step-1 xstep-1
		// alternadamente
		vector<int> aux;
		int last = min(n - 1, ini + step - 1);
		int cur_sz = last - ini + 1;
		for (int j = 0; j < cur_sz; j++) {
			aux.push_back({ini + j});
			int pos_to_use = using_b ? pos_B[j] : pos_A[j];
			aux.push_back(pos_to_use);
		}

		// cout << "will make query ";
		// for (int x: aux) {
		// 	cout << x << " ";
		// }
		// cout << endl;

		int ret = use_machine(aux);
		// cout << "got " << ret << endl;
		if (using_b) {
			ans += (ret + 1) / 2;
		} else {
			ans += cur_sz - (ret + 1) / 2;
		}
		ini += cur_sz;
		// cout << "now ans = " << ans << endl;
		// cout << "now ini = " << ini << endl;
	}

	return ans;
}

• Subtask 1: 80.427 / 100