제출 #631061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631061		kingmoshe	드문 곤충 (IOI22_insects)	C++17	0 / 100	1 ms	336 KiB

insects

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

/*void move_inside(int i) {

}*/
/*void move_outside(int i) {

}*/
/*int press_button() {

}*/
std::vector<bool> visited(0);
void init(int N) {
	visited.resize(N, false);
}
int get_number_of_types(int N) {
	move_inside(0);
	int counter = 0;
	visited[0] = true;
	for (int i = 1; i < N; i++) {
		move_inside(i);
		int value = press_button();
		if (value == 1) {
			visited[i] = true;
			counter += 1;
		}
		else {
			move_outside(i);
		}
	}
	return counter;
}
void remove_all_indexes(std::vector<int> indexes) {
	for (int i = 0; i < int(indexes.size()); i++) {
		move_outside(indexes[i]);
	}
}
int first_solution(int N) {
	int number_of_types = get_number_of_types(N);
	int current_result = 1;
	std::vector<int> inside_indexes(0);
	bool any_change = true;
	while (any_change) {
		any_change = false;
		for (int i = 0; i < N; i++) {
			if (visited[i]) {
				continue;
			}
			move_inside(i);
			int value = press_button();
			if (value > current_result + 1) {
				move_outside(i);
			}
			else {
				visited[i] = true;
				inside_indexes.push_back(i);
			}
			if (int(inside_indexes.size()) == number_of_types) {
				any_change = true;
				remove_all_indexes(inside_indexes);
			}
		}
		remove_all_indexes(inside_indexes);
		inside_indexes.resize(0);
	}
	return current_result;
}
int min_cardinality(int N) {
	init(N);
	return first_solution(N);
}

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