제출 #1180243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180243		Pacybwoah	Counting Mushrooms (IOI20_mushrooms)	C++20	80.71 / 100	3 ms	464 KiB

mushrooms

#include "mushrooms.h"
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

int count_mushrooms(int n) {
	int ans = 1;
	vector<int> a, b;
	a.push_back(0);
	int cur = 1;
	while(cur < n){
		int sa = (int)a.size(), sb = (int)b.size();
		if(sa >= sb){
			vector<int> ask;
			int ina = 0, imp = cur;
			for(int i = 0; i < sa; i++){
				if(cur == n) break;
				ask.push_back(cur);
				ask.push_back(a[i]);
				cur++;
				if(i > 0) ina++;
			}
			int res = use_machine(ask);
			if(res & 1){
				b.push_back(imp);
			}
			else{
				a.push_back(imp);
				ans++;
			}
			ans += ina - res / 2;
		}
		else{
			vector<int> ask;
			int imp = cur;
			for(int i = 0; i < sb; i++){
				if(cur == n) break;
				ask.push_back(cur);
				ask.push_back(b[i]);
				cur++;
			}
			int res = use_machine(ask);
			if(res & 1){
				a.push_back(imp);
				ans++;
			}
			else b.push_back(imp);
			ans += res / 2;
		}
	}
	return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g mushrooms.cpp stub.cpp

• Subtask 1: 80.7143 / 100