Submission #1042546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042546		Alihan_8	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	140 ms	920 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()

template <class F, class S>
bool chmin(F &u, const S &v){
	bool flag = false;
	
	if ( u > v ){
		u = v; flag |= true;
	}
	
	return flag;
}

const int C = 100;

int min_cardinality(int n) {
	vector <int> p;
	
	for ( int i = 0; i < n; i++ ){
		move_inside(i);
		
		if ( press_button() == 1 ){
			p.pb(i);
		} else{
			move_outside(i);
		}
	}
	
	int k = (int)p.size();
	
	for ( auto &x: p ){
		move_outside(x);
	} p.clear();
	
	auto ok = [&](int m){
		int cnt = 0;
		
		for ( int i = 0; i < n; i++ ){
			move_inside(i);
			
			if ( press_button() > m ){
				move_outside(i);
			} else{
				p.pb(i);
				cnt += 1;
			}
		}
		
		for ( auto &x: p ){
			move_outside(x);
		} p.clear();
		
		return cnt == k * m;
	};
	
	int l = 1, r = n + 1;
	
	while ( l + 1 < r ){
		int m = (l + r) / 2;
		
		if ( ok(m) ) l = m;
		else r = m;
	}
	
	return l;
}

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