Submission #1292727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292727		julia_08	Counting Mushrooms (IOI20_mushrooms)	C++20	10 / 100	51 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;

	int sz = n - 1;

	while((int) a.size() <= sz && (int) b.size() <= sz){

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

		sz --;

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

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

	}

	int cnt = 0;

	if((int) a.size() > sz){

		vector<int> to_ask;

		for(int i=0; i<sz; i++){
			to_ask.push_back(a[i]);
			to_ask.push_back(cur[i]);
		}

		to_ask.push_back(a[sz]);

		int ans = ask(to_ask);

		cnt = (int) a.size() + (sz - (ans / 2));

	} else{

		vector<int> to_ask;

		for(int i=0; i<sz; i++){
			to_ask.push_back(b[i]);
			to_ask.push_back(cur[i]);
		}

		to_ask.push_back(b[sz]);

		int ans = ask(to_ask);

		cnt = (int) a.size() + ans / 2;

	}

	return cnt;

}

• Subtask 1: 10 / 100