제출 #727231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727231		ismayil	드문 곤충 (IOI22_insects)	C++17	0 / 100	1 ms	208 KiB

insects

#pragma GCC optimize("O3")
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
//g++ -std=c++17 insects.cpp stub.cpp
int D, N;
const int MAX = 3000;
int mark[MAX];
int cnt = 0;
bool check(int m){
	vector<int> tmp, tmp1;
	for(int j = 0; j < N; j++){
		if(mark[j]) continue;
		move_inside(j);
		if(press_button() > m){
			move_outside(j);
			mark[j] = 1;
			tmp1.push_back(j);
		}else{
			cnt++;
			mark[j] = 1;
			tmp.push_back(j);
		}
		if(cnt >= m * D) return false;
	}
	if(cnt < m * D){
		cnt -= tmp.size();
		for(auto i : tmp) move_outside(i), mark[i] = 0;
		return true;
	}
	for(auto i : tmp1) mark[i] = 0;
	return false;
}
int min_cardinality(int n) {
	N = n;
	for(int j = 0; j < N; j++){
		move_inside(j);
		if(press_button() > 1){
			move_outside(j);
		}else{
			cnt++;
			mark[j] = 1;
		}
	}
	D = cnt;

	int l = 1, r = N / D;
	while(l <= r){
		int m = (l + r) / 2;
		if(check(m)) r = m - 1;
		else l = m + 1;
	}
	return r;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75