Submission #1191826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191826		ByeWorld	Rarest Insects (IOI22_insects)	C++20	99.79 / 100	16 ms	428 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;

int n, dif;
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(i);
		if(press() == x+1){
			out(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(i); ada[i] = 0;
			}
		}
		for(auto in : vec) tag[in] = 1;
	return 0;
}
int min_cardinality(int N) {
	n = N;

	int las;
	for(int i=0; i<n; i++){
		ins(i);
		if(press() != 1) out(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