Submission #837353

#	Time	Username	Problem	Language	Result	Execution time	Memory
837353		Sohsoh84	Rarest Insects (IOI22_insects)	C++17	73.33 / 100	124 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;
	shuffle(all(vec), rng);
	for (int i = 1; i <= n + 1; i++) {	
		int tsize = 0;	
		int ind = 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) {
					rotate(vec.begin(), vec.begin() + ind, vec.end());
					break;
				}
			
				ind++;
			}
		}

		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: 48.33 / 75