Submission #631121

#	Time	Username	Problem	Language	Result	Execution time	Memory
631121		kingmoshe	Rarest Insects (IOI22_insects)	C++17	0 / 100	55 ms	304 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<int> shuffle(0);
void move_inside2(int i) {
	move_inside(shuffle[i]);
}
void move_outside2(int i) {
	move_outside(shuffle[i]);
}
std::vector<bool> visited(0);
void init(int N) {
	visited.resize(N, false);
	shuffle.resize(N);
	for (int i = 0; i < N; i++) {
		shuffle[i] = i;
	}
	std::random_shuffle(shuffle.begin(), shuffle.end());
}
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 < int(inside_indexes.size()); i++) {
			visited[inside_indexes[i]] = false;
		}
		remove_all_indexes(inside_indexes);
		inside_indexes.resize(0);
	}
	return current_result;
}
int get_best_t(int size, int k) {
	int t = size / (k + k);
	t += 5;
	while (t * k * 2 > size) {
		t -= 1;
	}
	return t;
}
int second_solution(int N) {
	int k = get_number_of_types(N);
	int amount_left = N - k;
	int found_so_far = 1;
	while (true) {
		int t = get_best_t(amount_left, k);
		std::vector<int> inside_indexes(0);
		inside_indexes.resize(0);
		if (k > amount_left) {
			return found_so_far;
		}
		if (k + k > amount_left) {
			t = 1;
		}
		for (int i = 0; i < N; i++) {
			if (visited[i]) {
				continue;
			}
			move_inside(i);
			int value = press_button();
			if (value > t + found_so_far) {
				move_outside(i);
			}
			else {
				inside_indexes.push_back(i);
				visited[i] = true;
			}
			if (int(inside_indexes.size()) == k * t) {
				break;
			}
		}
		if (int(inside_indexes.size()) == k * t) {
			found_so_far += t;
			amount_left -= k * t;
		}
		else if (t == 1) {
			break;
		}
		else {
			for (int i = 0; i < N; i++) {
				visited[i] = true;
			}
			amount_left = 0;
			for (int i = 0; i<int(inside_indexes.size()); i++) {
				visited[inside_indexes[i]] = false;
				amount_left += 1;
			}
		}
	}
	return found_so_far;
}
int min_cardinality(int N) {
	init(N);
	return second_solution(N);
}
/*int main() {
	// 5, 8, 9,5 ,9 ,9
	maximal_type = 10;
	int n = 100;
	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();
}//*/

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