Submission #629083

#	Time	Username	Problem	Language	Result	Execution time	Memory
629083		handlename	Rarest Insects (IOI22_insects)	C++17	47.57 / 100	209 ms	536 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define pb push_back
#define mp make_pair
set<int> s;
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);
		}
	}
	int mini=1,maxi=n+1,sz=s.size();
	while (mini+1<maxi){
		int mid=(mini+maxi)/2;
		set<int> added;
		for (int i=0;i<n;i++){
			if (s.find(i)!=s.end()) continue;
			add(i);
			if (press_button()>mid) rem(i);
			else added.insert(i);
		}
		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: 22.57 / 75