Submission #837355

#	Time	Username	Problem	Language	Result	Execution time	Memory
837355		Sohsoh84	Rarest Insects (IOI22_insects)	C++17	90.41 / 100	87 ms	332 KiB

insects

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

using namespace std;

#define all(x)		(x).begin(), (x).end()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e6 + 10;

int n;
bool flag[MAXN];

int min_cardinality(int n_) {
	n = n_;

	vector<int> vec;
	for (int i = 0; i < n; i++)
		vec.push_back(i);
	
	int base_size = MAXN;
	for (int i = 1; i <= n + 1; i++) {	
		shuffle(all(vec), rng);
		int tsize = 0;	
		for (int e : vec) {
			if (!flag[e]) {
				move_inside(e);
				if (press_button() == i) tsize++, flag[e] = true;
				else move_outside(e);
			
				if (tsize == base_size) break;
			}
		}

		if (tsize < base_size) {
			if (base_size == MAXN) base_size = tsize;
			else return i - 1;
		}
	}

	return 0;
}

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