제출 #758859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758859		amunduzbaev	드문 곤충 (IOI22_insects)	C++17	99.76 / 100	53 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;
		if(mx == 1){
			int sz = 0;
			for(auto x : used){
				move_inside(x);
				if(press_button() > 1) move_outside(x);
				else sz++;
			}
			if(sz == cnt) res++; 
			break;
		}
		int mid = mx / 2;
		if(check(mid)){
			res += mid;
		}
	}
	
	return res;
}

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