Submission #1233211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233211		nicolo_010	Rarest Insects (IOI22_insects)	C++20	50.03 / 100	58 ms	708 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)

int min_cardinality(int N) {
	int in = 0;
	int d = 0;
	set<int> s;
	rep(b, 1, 2) {
		rep(i, 0, N) {
			move_inside(i);
			in++;
			int a = press_button();
			if (a > b) {
				move_outside(i);
				in--;
				s.insert(i);
			}
			else {
				d++;
			}
		}
	}
	int l = 1, r = N/d+1;
	int ans = 1;
	set<int> never, use;
	while (l <= r) {
		int m = (l+r)/2;
		v<int> getout;
		set<int> sm, nev;
		for (auto x : s) {
			if (nev.count(x)) continue;
			getout.push_back(x);
			move_inside(x);
			in++;
			int a = press_button();
			if (a > m) {
				in--;
				move_outside(x);
				nev.insert(x);
			}
			else {
				sm.insert(x);
			}
		}
		for (auto x : getout) s.erase(x);
		for (auto x : nev) s.insert(x);

		if (in == m*d) {
			ans = m;
			l = m+1;
			for (auto x : nev) s.insert(x);
			rep(i, 0, N) {
				if (!s.count(i)) use.insert(i);
			}
		}
		else {
			r=m-1;
			for (auto x : nev) never.insert(x);
			for (auto x : sm) {
				if (!use.count(x)) {
					move_outside(x);
					s.insert(x);
					in--;
				}
			}
		}
	}
	return ans;
}

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