제출 #1294439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294439		m_bezrutchka	버섯 세기 (IOI20_mushrooms)	C++20	56.93 / 100	7 ms	428 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 < 2 * k - 1; i++) {
		if (i >= n) return ((int) pos_A.size());

		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();
	}

	// 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: 56.927 / 100