Submission #737706

#	Time	Username	Problem	Language	Result	Execution time	Memory
737706		iee	Rarest Insects (IOI22_insects)	C++17	100 / 100	67 ms	336 KiB

insects

void move_inside(int i);
void move_outside(int i);
int press_button();
#include <bits/stdc++.h>
using namespace std;
const int MN = 2005;
mt19937 eng(time(0));
int num, k;
int a[MN];
bool b[MN], bu[MN];
void insert(int x) {
	++num;
	move_inside(x - 1);
}
void remove(int x) {
	--num;
	move_outside(x - 1);
}
int min_cardinality(int n) {
	for (int i = 1; i <= n; ++i) {
		insert(i);
		if (press_button() >= 2) {
			remove(i);
		} else {
			b[i] = 1;
			++k;
		}
	}
	if (k == 1)
		return n;
	int l = 2, r = n / k;
	while (l <= r) {
		int mid = l + r >> 1;
		for (int i = 1; i <= n; ++i)
			bu[i] = false, a[i] = i;
		shuffle(a + 1, a + n + 1, eng);
		for (int i = 1; i <= n; ++i)
			if (!b[a[i]]) {
				if (k * mid <= num) break;
				insert(a[i]);
				if (press_button() > mid) {
					remove(a[i]);
				} else {
					bu[a[i]] = 1;
				}
			}
		if (k * mid <= num) {
			l = mid + 1;
			for (int i = 1; i <= n; ++i)
				b[i] |= bu[i];
		} else {
			r = num / k;
			for (int i = 1; i <= n; ++i)
				if (bu[i]) {
					remove(i);
				} else {
					b[i] = 1;
				}
		}
	}
	return r;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid = l + r >> 1;
      |             ~~^~~

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