Submission #1232203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232203		kaltspielerhy	Rarest Insects (IOI22_insects)	C++20	0 / 100	1 ms	412 KiB

insects

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

int tailleCard(int N, vector<bool>& used) {
	int taille = 0;
	vector<int> list;
	for (int i = 0; i < N; i++) {
		if (!used[i]) {
			move_inside(i);
			if (press_button() != 1) {
				move_outside(i);
			}
			else {
				used[i] = true;
				taille++;
				list.push_back(i);
			}
		}
	}

	for (int i : list) move_outside(i);

	return taille;
}

int eliminate(int N, vector<bool>& used) {
	vector<int> list;
	for (int i = 0; i < N; i++) {
		if (!used[i]) {
			move_inside(i);
		}
	}

	int cardMax = press_button();

	for (int i = 0; i < N; i++) {
		if (!used[i]) {
			move_outside(i);
			if (press_button() < cardMax) {
				move_inside(i);
				used[i] = true;
				list.push_back(i);
			}
		}
	}

	for (int i : list) move_outside(i);

	return cardMax;
}

int min_cardinality(int N) {
	vector<bool> used(N);
	int last = tailleCard(N, used);
	int nbRestants = N-last;
	int nbOperations = 1;
	int cardAct = (nbRestants+last-1)/last;
	while (nbRestants > 0) {
		if (cardAct > last) {
			int result = eliminate(N, used);
			nbRestants -= result;
			last--;
			cardAct = (nbRestants+last-1)/(last);
			if (nbRestants == 0) {
				return result + nbOperations;
			}
		}
		else {
			int another = tailleCard(N, used);
			if (another != last) return nbOperations;
			nbOperations++;
			last = another;
			nbRestants -= last;
			cardAct = (nbRestants+last-1)/last;
		}
	}

	return nbOperations;
}

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