제출 #1191830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191830		ByeWorld	드문 곤충 (IOI22_insects)	C++20	99.79 / 100	15 ms	452 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define pb push_back
#define md ((l+r+1)>>1)
#define ins move_inside
#define out move_outside
#define press press_button
using namespace std;
const int MAXN = 2010;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, dif;
int arr[MAXN];
bool ada[MAXN], les[MAXN], tag[MAXN]; 
int cnt = 1;

bool ri = 0;

bool cek(int x){
	vector<int> vec;
	for(int i=0; i<n; i++){
		if(ada[i] || tag[i]) continue;

		ins(arr[i]);
		if(press() == x+1){
			out(arr[i]);
			vec.pb(i);
		} else {
			ada[i] = 1;
		}
	}

	int tot = 0;
	for(int i=0; i<n; i++) tot += ada[i];

	if(dif * x == tot){
		for(int i=0; i<n; i++)
			les[i] = ada[i];
		return 1;
	} 
		for(int i=0; i<n; i++){
			if(ada[i]==1 && les[i]==0){
				out(arr[i]); ada[i] = 0;
			}
		}
		for(auto in : vec) tag[in] = 1;
	return 0;
}
int min_cardinality(int N) {
	n = N;
	
	vector<int>V;
	for(int i=0; i<n; i++) V.pb(i);
	shuffle(V.begin(), V.end(), rng);

	for(int i=0; i<n; i++) arr[i] = V[i];

	int las;
	for(int i=0; i<n; i++){
		ins(arr[i]);
		if(press() != 1) out(arr[i]); // keluarin
		else {
			dif++; ada[i] = 1;
		}
	}
	for(int i=0; i<n; i++)
		les[i] = ada[i];

	int l=2, r=n/dif, mid=0; 
	while(l<=r){
		mid = md;
		if(cek(mid)){ 
			cnt = mid; l = mid+1; 
		} else {
			r = mid-1; 
		}
	}
	return cnt;
}

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