Submission #774561

#	Time	Username	Problem	Language	Result	Execution time	Memory
774561		GusterGoose27	Rarest Insects (IOI22_insects)	C++17	52.13 / 100	126 ms	456 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>

using namespace std;

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

int solve(int l, int r, vector<int> &reps, vector<int> &ex) {
	if (ex.empty()) return 1;
	if (l == r) return ex.size()+1;
	int mid = (l+r)/2;
	for (int i = mid+1; i <= r; i++) move_outside(reps[i]);
	vector<int> lex, rex;
	for (int v: ex) {
		move_inside(v);
		if (press_button() > 1) {
			lex.push_back(v);
		}
		else rex.push_back(v);
		move_outside(v);
	}
	int a = solve(l, mid, reps, lex);
	for (int i = l; i <= mid; i++) move_outside(reps[i]);
	for (int i = mid+1; i <= r; i++) move_inside(reps[i]);
	return min(a, solve(mid+1, r, reps, rex));
}

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)]);
	vector<int> reps;
	vector<int> extra;
	for (int i = 0; i < n; i++) {
		move_inside(perm[i]);
		if (press_button() > 1) {
			move_outside(perm[i]);
			extra.push_back(perm[i]);
		}
		else {
			skip[i] = 1;
			reps.push_back(perm[i]);
		}
	}
	return solve(0, reps.size()-1, reps, extra);
}

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