oj.uz

Submission #959347

# Submission time Handle Problem Language Result Execution time Memory
959347 2024-04-08T05:07:44 Z The_Samurai Counting Mushrooms (IOI20_mushrooms) C++17
0 / 100
 32 ms 1036 KB 
#include "mushrooms.h"
#include "bits/stdc++.h"
using namespace std;

int count_mushrooms(int n) {
	vector<int> zeros = {0};
	const int cnt = 4;
	while (zeros.size() < cnt) {
		if (zeros.back() == n - 1) break;
		if (use_machine({0, zeros.back() + 1}) == 0) {
			zeros.emplace_back(zeros.back() + 1);
			continue;
		}
		int lx = zeros.back() + 2, rx = n - 1, best = -1;
		int last_one = zeros.back() + 1;
		while (lx <= rx) {
			int mid = (lx + rx) >> 1;
			vector<int> v = {0};
			for (int i = last_one; i <= mid; i++) v.emplace_back(i);
			if (use_machine(v) >= 2) {
				best = mid;
				rx = mid - 1;
			} else {
				last_one = mid;
				lx = mid + 1;
			}
		}
		if (best == -1) break;
		zeros.emplace_back(best);
	}
	if (zeros.size() < cnt) return zeros.size();
	vector<int> unused;
	for (int i = zeros.back() + 1; i < n; i++) unused.emplace_back(i);
	int ans = zeros.size();
	while (!unused.empty()) {
		int ln = min(unused.size(), zeros.size());
		vector<int> v;
		for (int i = 0; i < ln; i++) {
			v.emplace_back(zeros[i]);
			v.emplace_back(unused.back());
			unused.pop_back();
		}
		ans += ln - (use_machine(v) + 1) / 2;
	}
	return ans;
}

// 0 -> 3
// 2 -

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Partially correct 3 ms 456 KB Output is partially correct
7 Partially correct 24 ms 444 KB Output is partially correct
8 Partially correct 24 ms 440 KB Output is partially correct
9 Partially correct 27 ms 1036 KB Output is partially correct
10 Partially correct 32 ms 548 KB Output is partially correct
11 Partially correct 27 ms 448 KB Output is partially correct
12 Partially correct 29 ms 552 KB Output is partially correct
13 Partially correct 31 ms 1000 KB Output is partially correct
14 Partially correct 12 ms 500 KB Output is partially correct
15 Incorrect 30 ms 780 KB Too many total array sizes as queries.
16 Halted 0 ms 0 KB -