Submission #1059985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059985		DorostWef	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	42 ms	856 KiB

insects

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

using namespace std;

int min_cardinality(int N) {
	vector <int> a;
	int n = N;
	int k = 0;
	vector <int> d;
	for (int i = 0; i < n; i++) {
		move_inside (i);
		if (press_button() >= 2) {
			move_outside (i);
			a.push_back(i);
		} else {
			d.push_back(i);
			k++;
		}
	}
	for (int i : d)
		move_outside (i);
	int ans = 1;
	while ((int)a.size() >= k) {
		n = (int)a.size();
//		cout << n << endl;
		int m = n / (k);
		m = (m + 1) / 2;
		int cnt = 0;
		vector <int> b, c;
		for (int i = 0; i < n; i++) {
			move_inside (a[i]);
			if (press_button() > m) {
				b.push_back (a[i]);
				move_outside (a[i]);
			} else {
				cnt++;
				c.push_back (a[i]);
			}
		}
		for (int i : c)
			move_outside (i);
		if (cnt == k * m) {
			a = b;
			ans += m;
		} else {
			a = c;
		}
	}
	return ans;
}

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