Submission #786192

#	Time	Username	Problem	Language	Result	Execution time	Memory
786192		khshg	Rarest Insects (IOI22_insects)	C++17	25 / 100	320 ms	432 KiB

insects

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

int min_cardinality_st1(int N) {
	vector<int> Ls{0}, cnt(N, 1);
	move_inside(0);
	for(int i = 1; i < N; ++i) {
		move_inside(i);
		int ks = press_button();
		if(ks == 1) { Ls.push_back(i); continue; }
		for(auto& u : Ls) {
			move_outside(u);
			ks = press_button();
			move_inside(u);
			if(ks == 1) {
				++cnt[u];
				break;
			}
		}
		move_outside(i);
	}
	int ans = 0x3f3f3f3f;
	for(auto& u : Ls) ans = min(ans, cnt[u]);
	return ans;
}

int min_cardinality(int N) {
	set<int> alr;
	int pr = -1;
	for(int j = 1;; ++j) {
		int cnt = 0;
		for(int i = 0; i < N; ++i) {
			if(!alr.insert(i).second) continue;
			move_inside(i);
			int ks = press_button();
			if(ks == j) { ++cnt; continue; }
			alr.erase(i);
			move_outside(i);
		}
		if(j > 1 && cnt != pr) {
			return j - 1;
		}
		pr = cnt;
		if(j == 1 && cnt <= 38) return min_cardinality_st1(N);
	}
	exit(-1);
	return -1;
}

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