Submission #1266775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266775		ThylOne	Rarest Insects (IOI22_insects)	C++17	100 / 100	15 ms	460 KiB

insects

//#define LOCAL
#include "insects.h"
#include <algorithm>
#include<bits/stdc++.h>

using namespace std;
#define pb push_back
set<int> bucket;
void push_in(int insect){
	assert(bucket.find(insect) == bucket.end());
	bucket.insert(insect);
	move_inside(insect);
}
void push_out(int insect){

	assert(bucket.find(insect) != bucket.end());
	bucket.erase(insect);
	move_outside(insect);
}
void empty_bucket(){
	for(int u:bucket){
		push_out(u);
	}
}
int min_cardinality(int N) {
	srand(42);
	bucket.clear();
	int D = 0;
	set<int> insect_q;
	for(int i = 0 ; i < N ; i++){
		push_in(i);
		if(press_button() == 1){D++;}
		else{insect_q.insert(i); push_out(i);}
	}
	
	//On va maintenant proceder a la dichotomie
	

	int low = 1 ;
	int high = N / D + 1;
	while(high - low > 1){
		vector<int> to_inspect;
		for(int u:insect_q)to_inspect.emplace_back(u);
		random_shuffle(to_inspect.begin(), to_inspect.end());
		int bound = (low + high)/2;
		vector<int> add_tturn, out;
		for(int i:to_inspect){
			push_in(i);
			int r = press_button();
			if(r > bound){
				push_out(i);
				out.push_back(i);
				continue;
			}
			
			add_tturn.push_back(i);
			if(bound*D == bucket.size())break;
		}
		if(bound*D==bucket.size()){
			low = bound;
			for(int u:add_tturn)insect_q.erase(u);
		}else{
			for(int u:add_tturn)push_out(u);
			for(int u:out)insect_q.erase(u);
			high = bound;
		}
	}

	return low;
}

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