제출 #629089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
629089		handlename	드문 곤충 (IOI22_insects)	C++17	53.16 / 100	193 ms	440 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define pb push_back
#define mp make_pair
set<int> s;
void add(int i){
	move_inside(i);
	s.insert(i);
}
void rem(int i){
	move_outside(i);
	s.erase(i);
}
int min_cardinality(int n){
	for (int i=0;i<n;i++){
		add(i);
		if (press_button()>1){
			rem(i);
		}
	}
	int mini=1,maxi=n/s.size()+1,sz=s.size();
	while (mini+1<maxi){
		int mid=(mini+maxi)/2;
		set<int> added;
		for (int i=0;i<n;i++){
			if (s.find(i)!=s.end()) continue;
			add(i);
			if (press_button()>mid) rem(i);
			else added.insert(i);
		}
		if ((int)s.size()==sz*mid){
			mini=mid;
		}
		else {
			maxi=mid;
			for (auto i:added) rem(i);
		}
	}
	return mini;
}

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