제출 #1180882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180882		Pacybwoah	버섯 세기 (IOI20_mushrooms)	C++20	0 / 100	0 ms	420 KiB

mushrooms

#include "mushrooms.h"
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
namespace{
	const int K = 90;
}
int count_mushrooms(int n) {
	int ans = 1;
	vector<int> a, b;
	a.push_back(0);
	int cur = 1;
	vector<int> askf = {0, 1};
	if(use_machine(askf) == 1){
		b.push_back(1);
	}
	else{
		ans++;
		a.push_back(1);
	}
	if(n == 2) return ans;
	if((int)a.size() < 2){
		askf = {0, 2};
		if(use_machine(askf) == 1){
			b.push_back(2);
		}
		else{
			ans++;
			a.push_back(2);
		}
	}
	cur = 3;
	while(cur + 1 < min(n, 2 * K)){
		int sa = (int)a.size(), sb = (int)b.size();
		if(sa >= 2){
			askf = {a[0], cur, a[1], cur + 1};
			int res = use_machine(askf);
			if(res & 1){
				b.push_back(cur + 1);
			}
			else{
				a.push_back(cur + 1);
			}
			if(res >= 2){
				b.push_back(cur);
			}
			else{
				a.push_back(cur);
			}
		}
		else{
			askf = {b[0], cur, b[1], cur + 1};
			int res = use_machine(askf);
			if(res & 1){
				a.push_back(cur + 1);
			}
			else{
				b.push_back(cur + 1);
			}
			if(res >= 2){
				a.push_back(cur);
			}
			else{
				b.push_back(cur);
			}
		}
		cur += 2;
	}
	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: 0 / 100