Submission #794364

#	Time	Username	Problem	Language	Result	Execution time	Memory
794364		IvanJ	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	209 ms	524 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int n, D;

int check(int x) {
	vector<int> in;
	for(int i = 0;i < n;i++) {
		move_inside(i);
		if(press_button() > x) 
			move_outside(i);
		else in.pb(i);
	}
	
	for(int i : in) move_outside(i);
	return ((int)in.size() == x * D);
}

int min_cardinality(int N) {
	n = N, D = 0;
	
	vector<int> v;
	for(int i = 0;i < n;i++) {
		move_inside(i);
		if(press_button() > 1) 
			move_outside(i);
		else v.pb(i), D++;
	}
	for(int i : v) move_outside(i);
	
	int lo = 2, hi = n, ans = 1;
	while(lo <= hi) {
		int mid = (lo + hi) / 2;
		if(check(mid)) 
			ans = mid, lo = mid + 1;
		else hi = mid - 1;
	}
	return ans;
}

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