Submission #893157

#	Time	Username	Problem	Language	Result	Execution time	Memory
893157		Trisanu_Das	Rarest Insects (IOI22_insects)	C++17	100 / 100	34 ms	960 KiB

insects

#pragma GCC optimize("O3")
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

int D, N;
const int MAX = 3000;
int mark[MAX], inside[MAX];
vector<int> p;
int cnt = 0;
bool check(int m){
	for(auto i : p){
		if(cnt == m * D) break;
		if(mark[i]) continue;
		move_inside(i);
		if(press_button() > m){
			move_outside(i);
		}else{
			cnt++;
			inside[i] = 1;
		}
	}
	if(cnt == m * D){
		for(int i = 0; i < N; i++) if(inside[i]) mark[i] = 1;
		return false;
	}
	for(int i = 0; i < N; i++){
		if(!inside[i]) mark[i] = 1;
		else if(!mark[i]){
			move_outside(i);
			inside[i] = 0;
			cnt--;
		}
	}
	return true;
}
int min_cardinality(int n) {
	N = n;
	p.resize(N);
	for(int i = 0; i < N; i++) p[i] = i;
	random_shuffle(p.begin(), p.end());
	for(int i = 0; i < N; i++){
		move_inside(i);
		if(press_button() > 1){
			move_outside(i);
		}else{
			cnt++;
			inside[i] = 1;
			mark[i] = 1;
		}
	}
	D = cnt;
 
	int l = 1, r = N / D;
	while(l <= r){
		int m = (l + r) / 2;
		if(check(m)) r = m - 1;
		else l = m + 1;
	}
	return r;
}

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