oj.uz

Submission #410277

# Submission time Handle Problem Language Result Execution time Memory
410277 2021-05-22T12:02:38 Z priority_queue Counting Mushrooms (IOI20_mushrooms) C++14
0 / 100
 21 ms 576 KB 
#include <bits/stdc++.h>

#define forint(i, N) for (int i = 0; i < (N); i++)

using namespace std;


int use_machine(vector<int> x);

int count(char first_char, int first, int last, int& n_diff) {
	if (first == last) {
		if (first_char == 'A') {
			return 1;
		}
		else {
			return 0;
		}
	}
	else {
		if (n_diff < 0) {
			vector<int> x;
			
			for (int i = first; i <= last; i++) {
				x.push_back(i);
			}			

			n_diff = use_machine(x);
		}

		int len = last - first + 1;
		if (n_diff == 0) {
			return (first_char == 'A' ? len : 0);
		}
		else if (n_diff == len-1) {		
			if (len % 2 == 0) {
				return len / 2;
			}
			else {
				if (first_char == 'A') {
					return len / 2 + 1;
				}
				else {
					return len / 2;
				}
			}
		}

		int mid = (first + last) / 2;

		int n_diff1 = -1;
		int n1 = count(first_char, first, mid, n_diff1);

		char c = n_diff1 % 2 == 0 ? first_char : ((first_char == 'A') ? 'B' : 'A');

		int n_diff2 = n_diff - n_diff1;

		int n2 = count(c, mid, last, n_diff2);
		
		if (c == 'A') {
			return n1 + n2 - 1;
		}
		else {
			return n1 + n2;
		}
	}
}

int count_mushrooms(int n) {

	int n_diff = -1;
	return count('A', 0, n - 1, n_diff);
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Partially correct 20 ms 200 KB Output is partially correct
7 Correct 12 ms 576 KB Output is correct
8 Incorrect 21 ms 456 KB Too many total array sizes as queries.
9 Halted 0 ms 0 KB -