Submission #776880

#	Time	Username	Problem	Language	Result	Execution time	Memory
776880		SanguineChameleon	Rarest Insects (IOI22_insects)	C++17	100 / 100	49 ms	428 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 gen(69420);
int D;

int solve(int K, vector<int> rem, int off) {
	shuffle(rem.begin(), rem.end(), gen);
	if (K == 0) {
		return 0;
	}
	int mid = (K + 1) / 2;
	vector<int> in, out;
	int cnt = 0;
	for (auto x: rem) {
		if (cnt == mid * D) {
			out.push_back(x);
			continue;
		}
		move_inside(x);
		if (press_button() > off + mid) {
			move_outside(x);
			out.push_back(x);
		}
		else {
			cnt++;
			in.push_back(x);
		}
	}
	if (cnt == mid * D) {
		return mid + solve(K - mid, out, off + mid);
	}
	else {
		for (auto x: in) {
			move_outside(x);
		}
		return solve(mid - 1, in, off);
	}
}

int min_cardinality(int N) {
	vector<int> rem;
	for (int i = 0; i < N; i++) {
		move_inside(i);
		if (press_button() == 2) {
			move_outside(i);
			rem.push_back(i);
		}
		else {
			D++;
		}
	}
	return 1 + solve(N / D - 1, rem, 1);
}

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