Submission #978472

#	Time	Username	Problem	Language	Result	Execution time	Memory
978472		Temmie	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	344 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>

std::vector <int> IN;

void inside(int x) {
	if (std::find(IN.begin(), IN.end(), x) == IN.end())
		IN.push_back(x), move_inside(x);
}

void outside(int x) {
	if (std::find(IN.begin(), IN.end(), x) != IN.end())
		IN.erase(std::find(IN.begin(), IN.end(), x)), move_outside(x);
}

int ask() {
	return press_button();
}

int min_cardinality(int n) {
	std::vector <int> in;
	for (int i = 0; i < n; i++) {
		inside(i);
		in.push_back(i);
		if (ask() == 1) continue;
		outside(i);
		in.pop_back();
	}
	std::vector <bool> not_in(n, true);
	for (int x : in) not_in[x] = false;
	int uniq = in.size();
	int ans = 1;
	for (int l = 2, r = n / uniq; l <= r; ) {
		int mid = (l + r) >> 1;
		in.clear();
		for (int i = 0; i < n; i++) {
			if (!not_in[i]) continue;
			inside(i);
			in.push_back(i);
			if (ask() > mid) {
				outside(i);
				in.pop_back();
				continue;
			}
		}
		if ((int) in.size() == uniq * mid) {
			ans = mid;
			l = mid + 1;
			not_in.assign(n, true);
			for (int x : in) not_in[x] = false;
		} else {
			r = mid - 1;
			not_in.assign(n, false);
			for (int x : in) not_in[x] = true;
			for (int x : in) {
				move_outside(x);
			}
		}
	}
	return ans;
}

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