Submission #1223123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223123		yuqzii	Rarest Insects (IOI22_insects)	C++20	53.13 / 100	49 ms	412 KiB

insects

#include "insects.h"
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int min_cardinality(int N) {
	int k = 0;
	stack<int> in;
	queue<int> out, discard;
	for (int i = 0; i < N; i++) out.push(i);
	for (int i = 0; i < N; i++) {
		int a = out.front();
		out.pop();
		move_inside(a);
		if (press_button() == 1) {
			++k;
			in.push(a);
		}
		else {
			move_outside(a);
			out.push(a);
		}
	}

	while (!in.empty()) {
		out.push(in.top());
		in.pop();
	}

	int l = 1, r = N / k + 1;
	while (l < r - 1) {
		while (!discard.empty()) {
			out.push(discard.front());
			discard.pop();
		}

		int x = (l + r) / 2;

		while (!out.empty()) {
			int a = out.front();
			out.pop();
			move_inside(a);
			if (press_button() > x) {
				move_outside(a);
				discard.push(a);
			} else in.push(a);
		}

		if (in.size() == k * x) {
			l = x;
		} else {
			r = x;
			while (!in.empty()) {
				int a = in.top();
				move_outside(a);
				in.pop();
				discard.push(a);
			}
		}
	}

	return l;
}

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