Submission #758855

#	Time	Username	Problem	Language	Result	Execution time	Memory
758855		amunduzbaev	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	60 ms	424 KiB

insects

#include "insects.h"

#ifndef EVAL
#include "stub.cpp"
#endif

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

int min_cardinality(int n) {
	vector<int> used, rem;
	for(int i=0;i<n;i++){
		move_inside(i);
		if(press_button() > 1){
			move_outside(i);
			rem.push_back(i);
		} else {
			used.push_back(i);
		}
	}
	int cnt = used.size();
	for(auto x : used){
		move_outside(x);
	}
	if(cnt == 1){
		return n;
	}
	
	swap(used, rem);
	
	auto check = [&](int mid){
		vector<int> in, rem;
		for(auto x : used){
			move_inside(x);
			if(press_button() > mid){
				move_outside(x);
				rem.push_back(x);
			} else {
				in.push_back(x);
			}
		}
		for(auto x : in) move_outside(x);
		
		if((int)in.size() < mid * cnt){
			swap(used, in);
			return false;
		} else {
			swap(used, rem);
			return true;
		}
	};
	
	int res = 1;
	while((int)used.size() >= cnt){
		int mx = (int)used.size() / cnt;
		int mid = (mx + 1) / 2;
		if(check(mid)){
			res += mid;
		}
	}
	
	return res;
}

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