Submission #631072

#	Time	Username	Problem	Language	Result	Execution time	Memory
631072		kingmoshe	Rarest Insects (IOI22_insects)	C++17	25 / 100	390 ms	296 KiB

insects

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


/*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 real_result() {
	std::vector<int> values(maximal_type + 1);
	for (int i = 0; i < types.size(); i++) {
		values[types[i]] += 1;
	}
	int result = 100000;
	for (int i = 0; i < values.size(); i++) {
		if (values[i] != 0 && values[i] < result) {
			result = values[i];
		}
	}
	return result;
}
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;
				inside_indexes.resize(0);
			}
		}
		for (int i = 0; i < inside_indexes.size(); i++) {
			visited[inside_indexes[i]] = false;
		}
		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 = 4;
	int n = 60;
	for (int i = 0; i < n; i++) {
		types.push_back(rand() % maximal_type);
	}
	//types = { 5 ,8 ,9 ,5 , 9,9, 8 };
	std::cout << min_cardinality(n) << std::endl;
	std::cout << real_result();
}//*/

Compilation message (stderr)

insects.cpp: In function 'int first_solution(int)':
insects.cpp:99:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (int i = 0; i < inside_indexes.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~

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