Submission #410230

#	Time	Username	Problem	Language	Result	Execution time	Memory
410230		priority_queue	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	91 ms	456 KiB

mushrooms

#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;
			if (first < last) {
				for (int i = first; i <= last; i++) {
					x.push_back(i);
				}
			}
			else {
				for (int i = first; i >= last; i--) {
					x.push_back(i);
				}	
			}

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


		int mid = (first + last) / 2;

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

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

		int n_diff2 = n_diff - n_diff1;

		int n2 = count(c, last, mid, n_diff2);

		char c_mid = n_diff1 % 2 == 0 ? first_char : ((first_char == 'A') ? 'B' : 'A');
		
		if (c_mid == '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