Submission #893139

#	Time	Username	Problem	Language	Result	Execution time	Memory
893139		Trisanu_Das	Rarest Insects (IOI22_insects)	C++17	99.95 / 100	30 ms	1664 KiB

insects

#include"insects.h"
#include<bits/stdc++.h>
using namespace std;
 
int min_cardinality(int N) {
	int k, diff = 0;
	set<int> in;
	for(int i = 0; i < N; ++i) {
		in.insert(i);
		move_inside(i);
		k = press_button();
		if(k == 2) {
			in.erase(i);
			move_outside(i);
			continue;
		}
		diff++;
	}
	int l = 1, r = N / diff;
	vector<bool> skp(N);
	while(l < r) {
		int mid = (l + r + 1) / 2;
		vector<int> lst_added, ws;
		for(int i = 0; i < N; ++i) {
			if(skp[i] || !in.insert(i).second) continue;
			move_inside(i);
			k = press_button();
			if(k > mid) {
				in.erase(i);
				move_outside(i);
				ws.push_back(i);
				continue;
			}
			lst_added.push_back(i);
			if(diff * mid == (int)in.size()) break;
		}
		if((int)in.size() < diff * mid) {
			r = mid - 1;
			if(l == r) continue;
			for(auto& u : lst_added) {
				in.erase(u);
				move_outside(u);
			}
			for(auto& u : ws) skp[u] = 1;
		} else l = mid;
	}
	return (l + r) / 2;
}

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