Submission #1220851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220851		brinton	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	1 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{1};
	vector<int> B;

	int i = 0;
	for (; i+1 < n; i++){
		int type = use_machine({i,i+1});
		if(type == 1){
			lastType = 1-lastType;
		}
		if(lastType == 0) A.push_back(i+1);
		else B.push_back(i+1);
		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)/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: 0 / 100