Submission #1220854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220854		brinton	Counting Mushrooms (IOI20_mushrooms)	C++20	25 / 100	20 ms	420 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 = 3;
	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()]);
		// cout << "!";for(auto &i:unknown) cout << i << " "; cout << endl;
		// cout << "!!";for(auto &i:qry) cout << i << " "; cout << endl;
		return use_machine(qry)/2;
	};
	int tot = A.size();
	// for(auto &i:A) cout << i << " ";cout << endl;
	// for(auto &i:B) cout << i << " ";cout << endl;
	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: 25 / 100