제출 #1220860

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

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
// A:0,B:1
int count_mushrooms(int n) {
	int lastType = 0;
	int BlockSize = 100;
	vector<int> A{0};
	vector<int> B;

	int i = 1;
	for (; i < n; i++){
		int type = use_machine({i-1,i});
		if(type == 1){
			lastType = 1-lastType;
		}
		if(lastType == 0) A.push_back(i);
		else B.push_back(i);
		if(A.size() >= BlockSize || B.size() >= BlockSize) break;
	}

	
	auto merge_ask = [&](vector<int> unknown,vector<int> same){
		vector<int> qry;
		for(int j = 0;j < unknown.size();j++){
			qry.push_back(same[j]);
			qry.push_back(unknown[j]);
		}
		// qry.push_back(same[unknown.size()]);
		return (use_machine(qry)+1)/2;
	};
	int tot = A.size();
	i++;
	vector<int> cur;
	for(;i < n;i++){
		if(cur.size() == BlockSize){
			if(A.size() > B.size()){
				int diff = merge_ask(cur,A);
				tot += cur.size()-diff;
			}else{
				int diff = merge_ask(cur,B);
				tot += diff;
			}
			cur.clear();
		}
		cur.push_back(i);
	}
	if(cur.empty()) return tot;
	if(A.size() > B.size()){
		int diff = merge_ask(cur,A);
		tot += cur.size()-diff;
	}else{
		int diff = merge_ask(cur,B);
		tot += diff;
	}
	return tot;
}

• Subtask 1: 56.927 / 100