제출 #1292756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292756		julia_08	버섯 세기 (IOI20_mushrooms)	C++20	53.18 / 100	4 ms	616 KiB

mushrooms

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

using namespace std;

const int SQ = 140;

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

int solve(vector<int> &cur, vector<int> &a, vector<int> &b){

	int cnt = 0;

	vector<int> to_ask;

	int sz = 0;

	int l = 0;

	while(!cur.empty() && l < (int) a.size() - 1){

		to_ask.push_back(a[l++]);
		to_ask.push_back(cur.back());

		sz ++;
		cur.pop_back();

	}

	if(l < (int) a.size()) to_ask.push_back(a[l++]);

	int ans = ask(to_ask);

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

	sz = (int) cur.size();

	to_ask.clear();

	l = 0;

	while(!cur.empty()){

		to_ask.push_back(b[l++]);
		to_ask.push_back(cur.back());

		cur.pop_back();

	}

	if(l < (int) b.size()) to_ask.push_back(b[l++]);

	ans = ask(to_ask);

	cnt += ans / 2;

	return cnt;

}

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(!cur.empty() && (int) a.size() + (int) b.size() < SQ + 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);

	}

	vector<vector<int>> all_curs;

	all_curs.push_back({});

	int sz = (int) a.size() - 1 + (int) b.size() - 1;

	for(auto x : cur){

		if((int) all_curs.back().size() < sz){
			all_curs.back().push_back(x);
		} else all_curs.push_back({x});

	}

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

	for(auto cur : all_curs) tot += solve(cur, a, b);

	return tot;

}

• Subtask 1: 53.1765 / 100