제출 #1295196

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

mushrooms

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

using namespace std;

int get_ans(int sz, int ans, int x){
	if(x == 0) return sz / 2 - (ans + 1) / 2;
	return (ans + 1) / 2;
}

int count_mushrooms(int n){

	int x = 0;

	vector<int> pos[2];

	int k = 80;

	int cnt = 2 * k - 1;

	int tot = 0;

	if(cnt > n){

		for(int i=1; i<n; i++){
			vector<int> ask = {0, i};
			tot += (use_machine(ask) == 0);
		}

		return tot + 1;

	}

	pos[x].push_back(0);

	for(int i=1; i<3; i++){

		vector<int> ask = {0, i};

		if(use_machine(ask) == 0){
			pos[0].push_back(i);
		} else pos[1].push_back(i);

	}

	for(int i=3; i<cnt; i+=2){

		if((int) pos[1 - x].size() > (int) pos[x].size()) x = 1 - x;

		vector<int> ask = {pos[x][0], i, pos[x][1], i + 1};

		int cur = use_machine(ask);

		if(cur % 2 == 1){
			pos[1 - x].push_back(i + 1);
		} else pos[x].push_back(i + 1);

		cur /= 2;

		if(cur == 1){
			pos[1 - x].push_back(i);
		} else pos[x].push_back(i);

	}

	tot += (int) pos[0].size();

	for(int i=cnt; i<n; i++){

		if((int) pos[1 - x].size() > (int) pos[x].size()) x = 1 - x;

		vector<int> ask;

		int sz = (int) pos[x].size();

		for(int j=i; j<min(i + sz, n); j++){
			ask.push_back(pos[x][j - i]);
			ask.push_back(j);
		}

		i = min(i + sz, n) - 1;

		int cur = use_machine(ask);

		tot += get_ans((int) ask.size(), cur, x);

		if(cur % 2 == 1){
			pos[1 - x].push_back(i);
		} else pos[x].push_back(i);

	}

	return tot;

}

• Subtask 1: 92.623 / 100