Submission #1294438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294438		m_bezrutchka	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	2 ms	408 KiB

mushrooms

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

// ideias:
// - encontrar um conjunto de caras com mesmo valor
// - usar eles como "separadores" para contar desconhecidos
//
// passo 1:
//	 2k - 2 queries [0, i] para encontrar k iguais
//   entre os 2k - 1 primeiros
//
// passo 2:
// agora sobraram n - 2k + 1 ainda pra contar
// 	 #queries adicionais = teto( (n - 2k + 1) / k )
//
// otimizacao:
// 	minimize 2k - 2 + (n - 2k + 1) / k
//  	       = 2k + (n + 1)/k - 4
//    	     ~ 2k + n/k
//         
// 	minimize 2k + n/k
// 	2k = n/k
// 	k = sqrt(n / 2)
// 	k = 100
//
// total:
// 	198 queries para encontrar 100 iguais entre os 199 primeiros
// 	teto[(20000 - 199) / 100] = 199 queries pro resto
//  198 + 199 = 397 queries

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

	vector<int> pos_A;
	vector<int> pos_B;
	pos_A.push_back(0);

	int k = 100;

	// passo 1
	for (int i = 1; i < min(n, 2 * k - 1); i++) {
		if (use_machine({0, i}) == 0) pos_A.push_back(i);
		else pos_B.push_back(i);
	}

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

	int ans = pos_A.size();
	if (2 * k - 1 >= n) return ans;

	for (int ini = 2 * k - 1; ini < n; ini += step) {
		// ini x0 ini+1 x1 ini+2 x2 ... ini+step-1 xstep-1
		// alternadamente
		vector<int> aux;
		int l = ini, r = min(n - 1, ini + step - 1);
		int cur_sz = r - l + 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);
		}

		int ret = use_machine(aux);
		if (using_b) {
			ans += ret;
		} else {
			ans += cur_sz - ret;
		}
	}

	return ans;
}

• Subtask 1: 0 / 100