제출 #1125200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125200		StefanSebez	드문 곤충 (IOI22_insects)	C++17	99.57 / 100	22 ms	420 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
int min_cardinality(int n) {
	vector<int>vals;
	for(int i=0;i<n;i++){
		vals.pb(i);move_inside(i);
		if(press_button()==2) vals.pop_back(),move_outside(i);
	}
	int S=vals.size(),res;
	bool skip[n+10]={false},ubacen[n+10]={false};
	int l=1,r=n/S+1;
	while(l<=r){
		int mid=l+r>>1,ct=0;
		for(int i=0;i<n;i++) if(ubacen[i]) ct++;
		vector<int>a,b;
		for(int i=0;i<n;i++){
			if(ubacen[i]||skip[i]) continue;
			a.pb(i);move_inside(i);
			if(press_button()>mid) a.pop_back(),b.pb(i),move_outside(i);
			if(a.size()+ct==mid*S) break;
		}
		if(a.size()+ct==mid*S){
			res=mid;l=mid+1;
			for(auto i:a) ubacen[i]=true;
		}
		else{
			r=mid-1;
			for(auto i:a) move_outside(i);
			for(auto i:b) skip[i]=true;
		}
	}
	return res;
}

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