Submission #1125205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125205		StefanSebez	Rarest Insects (IOI22_insects)	C++17	99.61 / 100	22 ms	440 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
mt19937 rng(time(0));
int min_cardinality(int n) {
	vector<int>vals;
	for(int i=0;i<n;i++){
		vals.pb(i);move_inside(i);
		if(press_button()==2) vals.pop_back(),move_outside(i);
	}
	int S=vals.size();
	bool skip[n+10]={false},ubacen[n+10]={false};
	int l=1,r=n/S+1,res=1;
	while(l<=r){
		int mid=l+r>>1,ct=0;
		for(int i=0;i<n;i++) if(ubacen[i]) ct++;
		vector<int>a,b,ind;
		for(int i=0;i<n;i++) if(!skip[i]&&!ubacen[i]) ind.pb(i);
		shuffle(ind.begin(),ind.end(),rng);
		for(auto i:ind){
			if(ubacen[i]||skip[i]) continue;
			a.pb(i);move_inside(i);
			if(press_button()>mid) a.pop_back(),b.pb(i),move_outside(i);
			if(a.size()+ct==mid*S) break;
		}
		if(a.size()+ct==mid*S){
			res=mid;l=mid+1;
			for(auto i:a) ubacen[i]=true;
		}
		else{
			for(auto i:a) move_outside(i);
			for(auto i:b) skip[i]=true;
			r=mid-1;
			ct=0;for(int i=0;i<n;i++) if(!skip[i]) ct++;
			r=min(r,ct/S+1);
		}
	}
	return res;
}

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