Submission #631727

#	Time	Username	Problem	Language	Result	Execution time	Memory
631727		rainboy	Rarest Insects (IOI22_insects)	C++17	100 / 100	58 ms	328 KiB

insects

/* https://ioi2022.id/data/editorial.pdf */
#include "insects.h"

const int N = 2000;

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ii[N]; char type[N];

int min_cardinality(int n) {
	int d = 0;
	for (int i = 0; i < n; i++) {
		move_inside(i), type[i] = 1, d++;
		if (press_button() > 1)
			move_outside(i), type[i] = 0, d--;
	}
	int lower = 1, upper = n / d + 1, k = d;
	while (upper - lower > 1) {
		int c = (lower + upper) / 2, m = 0;
		for (int i = 0; i < n; i++)
			if (type[i] == 0)
				ii[m++] = i;
		for (int h = 0; h < m; h++) {
			int h_ = rand_() % (h + 1), tmp;
			tmp = ii[h], ii[h] = ii[h_], ii[h_] = tmp;
		}
		for (int h = 0; h < m; h++) {
			int i = ii[h];
			move_inside(i), type[i] = -1, k++;
			if (press_button() > c)
				move_outside(i), type[i] = 0, k--;
			else if (k == c * d)
				break;
		}
		if (k == c * d) {
			lower = c;
			for (int i = 0; i < n; i++)
				if (type[i] == -1)
					type[i] = 1;
		} else {
			upper = k / d + 1;
			for (int i = 0; i < n; i++)
				if (type[i] == -1)
					move_outside(i), type[i] = 0, k--;
				else if (type[i] == 0)
					type[i] = -2;
		}
	}
	return lower;
}

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