Submission #774547

#	Time	Username	Problem	Language	Result	Execution time	Memory
774547		GusterGoose27	Rarest Insects (IOI22_insects)	C++17	10 / 100	273 ms	320 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
bool skip[MAXN];

int min_cardinality(int n) {
    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);
    mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 1; i < n; i++) swap(perm[i], perm[gen()%(i+1)]);
	int mn = n;
	int num_found = 0;
	while (num_found < n) {
		// cerr << num_found << "\n";
		int num = 0;
		vector<int> inside;
		for (int i = 0; i < n; i++) {
			if (skip[i]) continue;
			move_inside(i);
			if (press_button() != num+1) move_outside(i);
			else {
				num++;
				inside.push_back(i);
			}
		}
		if (num == 1) return 1;
		num_found += num;
		for (int v: inside) {
			skip[v] = 1;
			move_outside(v);
		}
		mn = min(mn, num);
	}
	return mn;
}

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