Submission #831203

#	Time	Username	Problem	Language	Result	Execution time	Memory
831203		tolbi	Rarest Insects (IOI22_insects)	C++17	98.54 / 100	58 ms	528 KiB

insects

#include <bits/stdc++.h>
using namespace std;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "insects.h"
int min_cardinality(int n) {
	set<int> olan;
	for (int i = 0; i < n; ++i)
	{
		olan.insert(i);
	}
	vector<int> aldim;
	vector<int> almadim;
	function<int(int)> calc;
	calc = [&](int x)->int{
		aldim.clear();
		almadim.clear();
		int ans = 0;
		for (auto it : olan){
			move_inside(it);
			if (press_button()>x){
				move_outside(it);
				almadim.push_back(it);
			}
			else {
				aldim.push_back(it);
				ans++;
			}
		}
		for (auto &it : aldim){
			move_outside(it);
		}
		return ans;
	};
	int diff = calc(1);
	int l = 2, r = (n/diff)+1;
	int hueh = 0;
	while (l<r){
		int mid = l+(r-l)/2;
		int crr = calc(mid-hueh);
		if (crr==(mid-hueh)*diff){
			l=mid+1;
			hueh=mid;
			while (aldim.size()){
				olan.erase(aldim.back());
				aldim.pop_back();
			}
		}
		else {
			r=mid;
			while (almadim.size()){
				olan.erase(almadim.back());
				almadim.pop_back();
			}
		}
	}
	return l-1;
}

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