Submission #758848

#	Time	Username	Problem	Language	Result	Execution time	Memory
758848		amunduzbaev	Rarest Insects (IOI22_insects)	C++17	0 / 100	41 ms	464 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);
	}
	
	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);
			}
		}
		
		if((int)in.size() < mid * cnt){
			swap(used, in);
			for(auto x : used) move_outside(x);
			return false;
		} else {
			swap(used, rem);
			for(auto x : in) move_outside(x);
			return true;
		}
	};
	
	int l = 0, r = (n - cnt) / cnt;
	int res = 1;
	while(l < r){
		int old = used.size();
		int mid = (l + r + 1) >> 1;
		if(check(mid)){
			res += mid;
			l = 0, r -= mid;
		} else {
			r = mid - 1;
		}
		
		assert((int)used.size() <= (old + 1) / 2);
	}
	
	return res;
}

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