Submission #798976

#	Time	Username	Problem	Language	Result	Execution time	Memory
798976		AlphaBruh	Rarest Insects (IOI22_insects)	C++17	99.76 / 100	53 ms	420 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int k = 0;
int min_cardinality(int n) {
	move_inside(0);
	k++;
	vector<bool>in_m(2001,0);
	in_m[0]=1;
	for(int i = 1; i < n; i++){
		move_inside(i);
		int rt = press_button();
		if(rt==2){
			move_outside(i);
		}
		else{
			k++;
			in_m[i]=1;
		}
	}
	int ansl = 0, ansr = n/k,inmn=0,linmn;
	vector<int>nc;
	for(int i = 0; i < n; i++){
		nc.push_back(i);
	}

	while(ansl < ansr){
		linmn=inmn;
		int mid =ansl+((nc.size()/k)+1)/2;
		vector<int>im;
		vector<int>om;
		for(int i : nc){
			if(in_m[i]){
				inmn++;
				im.push_back(i);
				continue;
			}
			move_inside(i);
			int rt = press_button();
			if(rt > mid){
				move_outside(i);
				om.push_back(i);
			}
			else{
				in_m[i]=1;
				im.push_back(i);
				inmn++;
			}
		}
		if(inmn < k*mid){
			inmn = linmn;
			ansr = mid-1;
			for(int i : im){
				in_m[i]=0;
				move_outside(i);
			}
			nc.assign(im.begin(),im.end());
		}
		else{
			ansl = mid;
			nc.assign(om.begin(),om.end());
		}
	}
	return ansl;
}

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