Submission #641268

#	Time	Username	Problem	Language	Result	Execution time	Memory
641268		jamezzz	Rarest Insects (IOI22_insects)	C++17	100 / 100	61 ms	336 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

bool in[2005],bad[2005];
mt19937 rng(218);

int min_cardinality(int N){
	int types=0;
	for(int i=0;i<N;++i){
		move_inside(i);
		in[i]=true;
		if(press_button()>1){
			move_outside(i);
			in[i]=false;
		}
		else ++types;
	}
	int lo=2,hi=N/types,mid,res=1;
	vector<int> add;
	int tot=types;
	vector<int> index;
	for(int i=0;i<N;++i){
		index.push_back(i);
	}
	while(lo<=hi){
		mid=(lo+hi)>>1;
		add.clear();
		vector<int> newbad;
		shuffle(index.begin(),index.end(),rng);
		for(int i:index){
			if(in[i]||bad[i])continue;
			move_inside(i);
			in[i]=true;
			++tot;
			if(press_button()>mid){
				move_outside(i);
				in[i]=false;
				newbad.push_back(i);
				--tot;
			}
			else add.push_back(i);
			if(tot==mid*types)break;
		}
		if(tot==mid*types){
			res=mid;
			lo=mid+1;
		}
		else{
			hi=min(mid-1,tot/types);
			for(int i:add){
				move_outside(i);
				in[i]=false;
				--tot;
			}
			for(int i:newbad){
				bad[i]=true;
			}
		}
	}
	return res;
}

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