Submission #1233585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233585		colossal_pepe	Counting Mushrooms (IOI20_mushrooms)	C++20	56.93 / 100	3 ms	428 KiB

mushrooms

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

const int Q = 200;

int n;

vector<int> findKnowns() {
	vector<int> ret_A = {0}, ret_B;
	for (int i = 1; i < min(n, Q); i++) {
		if (use_machine(vector<int>{0, i})) ret_B.push_back(i);
		else ret_A.push_back(i);
	}
	return (ret_A.size() > ret_B.size() ? ret_A : ret_B);
}



int count_mushrooms(int N) {
	n = N;
	vector<int> known = findKnowns();
	int k = known.size(), cnt = (known[0] ? min(n, Q) - k : k);
	for (int i = Q; i < n; i += k) {
		vector<int> v;
		for (int j = i; j < min(n, i + k); j++) {
			v.push_back(known[j - i]), v.push_back(j);
		}
		int c = use_machine(v);
		if (v[0]) { // B 
			cnt += c % 2;
			cnt += c / 2;
		} else { // A
			cnt += !(c % 2);
			cnt += (min(n, i + k) - i - 1) - (c / 2);
		}
	}
	return cnt;
}

• Subtask 1: 56.927 / 100