Submission #303692

#	Time	Username	Problem	Language	Result	Execution time	Memory
303692		gs14004	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	12 ms	404 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int THR = 79 * 2 + 3;

int count_mushrooms(int n) {
	if(n <= 400){
		int cnt = 1;
		for(int i=1; i+1<n; i+=2){
			cnt += 2 - use_machine({i + 1, 0, i});
		}
		if(n % 2 == 0) cnt += 1 - use_machine({0, n - 1});
		return cnt;
	}
	vector<int> A, B;
	A.push_back(0);
	if(!use_machine({0, 1})) A.push_back(1);
	else B.push_back(1);
	if(!use_machine({0, 2})) A.push_back(2);
	else B.push_back(2);
	bool flag = 0;
	if(sz(A) == 1){
		flag = 1;
		swap(A, B);
	}
	for(int i = 3; i < THR; i += 2){
		int kek = use_machine({A[0], i, A[1], i + 1});
		if(kek & 2) B.push_back(i);
		else A.push_back(i);
		if(kek & 1) B.push_back(i + 1);
		else A.push_back(i + 1);
	}
	if(flag) swap(A, B);
	int pos = THR;
	int surplus = 0;
	while(pos < n){
		vector<int> kek;
		for(int i = 0; i < max(sz(A), sz(B)); i++){
			kek.push_back(pos);
			pos++;
			if(pos == n) break;
		}
		if(sz(A) >= sz(B)){
			vector<int> ans;
			for(int i = 0; i < sz(kek); i++){
				ans.push_back(kek[i]);
				ans.push_back(A[i]);
			}
			int q = use_machine(ans);
			surplus += sz(kek) - 1 - (q / 2);
			if(q & 1) B.push_back(kek[0]);
			else A.push_back(kek[0]);
		}
		else{
			vector<int> ans;
			for(int i = 0; i < sz(kek); i++){
				ans.push_back(kek[i]);
				ans.push_back(B[i]);
			}
			int q = use_machine(ans);
			surplus += (q / 2);
			if(q & 1) A.push_back(kek[0]);
			else B.push_back(kek[0]);
		}
	}
	return sz(A) + surplus;;
}

• Subtask 1: 92.623 / 100