Submission #1292744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292744		julia_08	Counting Mushrooms (IOI20_mushrooms)	C++20	25 / 100	29 ms	808 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"

using namespace std;

int ask(vector<int> &v){
	if((int) v.size() < 2) return 0;
	return use_machine(v);
}

int count_mushrooms(int n){

	vector<int> cur;

	for(int i=1; i<n; i++) cur.push_back(i);

	vector<int> a = {0}, b;

	while((int) a.size() + (int) b.size() < (int) cur.size() + 2){

		int v = cur.back();
		cur.pop_back();

		vector<int> to_ask = {0, v};

		if(ask(to_ask) == 0){
			a.push_back(v);
		} else b.push_back(v);

	}

	int cnt = 0;

	vector<int> to_ask;

	int sz_a = (int) a.size();

	int sz = 0;

	while(!cur.empty() && a.size() > 1){

		to_ask.push_back(a.back());
		to_ask.push_back(cur.back());

		sz ++;

		a.pop_back();
		cur.pop_back();

	}

	if(!a.empty()){
		to_ask.push_back(a.back());
		a.pop_back();
	}

	int ans = ask(to_ask);

	cnt += sz_a + (sz - (ans / 2));

	sz = (int) cur.size();

	to_ask.clear();

	while(!cur.empty()){

		to_ask.push_back(b.back());
		to_ask.push_back(cur.back());

		b.pop_back();
		cur.pop_back();

	}

	if(!b.empty()){
		to_ask.push_back(b.back());
		b.pop_back();
	}

	ans = ask(to_ask);

	cnt += ans / 2;

	return cnt;

}

• Subtask 1: 25 / 100