Submission #303667

#	Time	Username	Problem	Language	Result	Execution time	Memory
303667		aljasdlas	Counting Mushrooms (IOI20_mushrooms)	C++14	25 / 100	185 ms	596 KiB

mushrooms

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

int count_mushrooms(int n) {
	if(n < 220) {
		int B = 0;
		for(int i = 1; i < n; i++) {
			B += use_machine({0, i});
		}
		return n-B;
	}

	vector<int> A, B;
	A = {0};
	if(use_machine({0,1})) B.push_back(1);
	else A.push_back(1);
	if(use_machine({0,2})) B.push_back(2);
	else A.push_back(2);

	if(B.size() > A.size()) swap(A,B);

	for(int i = 3; i < n; i+=2) {
		vector<int> cur;
		cur.push_back(A[0]);
		cur.push_back(i);
		cur.push_back(A[1]);
		if(i+1 < n) cur.push_back(i+1);

		int res = use_machine(cur);

		if(res & 2) B.push_back(i);
		else A.push_back(i);

		if(i+1 < n) {
			if(res & 1) B.push_back(i);
			else A.push_back(i);
		}
	}


	if(A[0] == 0) return A.size();
	else return B.size();
}

• Subtask 1: 25 / 100