Submission #629091

#	Time	Username	Problem	Language	Result	Execution time	Memory
629091		handlename	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	78 ms	1360 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define pb push_back
#define mp make_pair
set<int> s;
set<int> lol[2001];
void add(int i){
	move_inside(i);
	s.insert(i);
}
void rem(int i){
	move_outside(i);
	s.erase(i);
}
int min_cardinality(int n){
	for (int i=0;i<n;i++){
		add(i);
		if (press_button()>1){
			rem(i);
		}
		lol[n].insert(i);
	}
	int mini=1,maxi=(n-n%(int)s.size())/s.size()+1,sz=s.size();
	while (mini+1<maxi){
		int mid=(mini+maxi)/2;
		set<int> added;
		int id=mid;
		for (int i=mid;i<=n;i++){
			if (!lol[i].empty()){
				id=i;
				break;
			}
		}
		for (auto i:lol[id]){
			if (s.find(i)!=s.end()) continue;
			add(i);
			if (press_button()>mid) rem(i);
			else added.insert(i);
		}
		lol[mid]=s;
		if ((int)s.size()==sz*mid){
			mini=mid;
		}
		else {
			maxi=mid;
			for (auto i:added) rem(i);
		}
	}
	return mini;
}

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