제출 #631071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631071		kingmoshe	Rarest Insects (IOI22_insects)	C++17	0 / 100	27 ms	208 KiB

insects

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


/*std::vector<int> types(0);
std::vector<int> inside(0);
int maximal_type = 0;

void move_inside(int i) {
	inside.push_back(i);
}
void move_outside(int i) {
	for (int j = 0; j < inside.size(); j++) {
		if (inside[j] == i) {
			inside.erase(inside.begin() + j);
			break;
		}
	}
}
int press_button() {
	std::vector<int> values(maximal_type + 1);
	int max_res = 0;
	for (int i = 0; i < inside.size(); i++) {
		values[types[inside[i]]] += 1;
		if (values[types[inside[i]]] > max_res) {
			max_res = values[types[inside[i]]];
		}
	}
	return max_res;
}//*/
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 = 1;
	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) {
				current_result += 1;
				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);
}
/*int main() {
	// 5, 8, 9,5 ,9 ,9
	maximal_type = 9;
	types = { 5 ,8 ,9 ,5 , 9,9, 8 };
	std::cout << min_cardinality(7);
}//*/

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