Submission #1078202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078202		UmairAhmadMirza	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	48 ms	972 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N){
	int type=0;
	set<int> in,out;
	for(int i=0;i<N;i++){
		move_inside(i);
		in.insert(i);
		if(press_button()>1){
			move_outside(i);
			in.erase(i);
		}
		else
			type++;
	}
	for (int i = 0; i < N; ++i)
		out.insert(i);
	for(int i:in)
		out.erase(i);
	in.clear();
	int low=1,high=(N/type)+1;
	int bef=type;
	while(high-low>1){
		int mid=(high+low)/2;
		int cnt=0;
		for(int i:out){
			move_inside(i);
			in.insert(i);
			if(press_button()>mid){
				move_outside(i);
				in.erase(i);
			}
			else
				cnt++;
			// if(cnt+bef==type*mid)
			// 	break;
		}
		if(cnt+bef==type*mid){
			mid=max(mid,((cnt+bef)/type));
			low=mid;
			if(high-low<=1)
				break;
			bef+=cnt;
			for(int i:in)
				out.erase(i);
			in.clear();
		}
		else{
			mid=min(((cnt+bef)/type)+1,mid);
			high=mid;
			if(high-low<=1)
				break;
			out.clear();
			for(int i:in){
				move_outside(i);
				out.insert(i);
			}
			in.clear();
		}
	}
	return low;
}

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