Submission #947740

#	Time	Username	Problem	Language	Result	Execution time	Memory
947740		biank	Rarest Insects (IOI22_insects)	C++17	100 / 100	37 ms	1872 KiB

insects

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)

void move_inside(int i);
void move_outside(int i);
int press_button();

stack<int> in;
set<int> s;
int T;

bool check(int m, int &K) {
	int oldK = K;
	vector<int> v(all(s));
	random_shuffle(all(v));
	for (int i:v) {
		move_inside(i);
		if (press_button() <= m) {
			in.push(i);
			if (++K == m*T) {
				while (!in.empty()) {
					s.erase(in.top());
					in.pop();
				}
				return true;
			}
		} else {
			move_outside(i);
		}
	}
	s.clear();
	while (!in.empty()) {
		s.insert(in.top());
		move_outside(in.top());
		in.pop();
	}
	K = oldK;
	return false;
}

int min_cardinality(int N) {
	srand(time(0));
	move_inside(0);
	in.push(0);
	s.insert(0);
	T = 1;
	for (int i = 1; i < N; i++) {
		s.insert(i);
		move_inside(i);
		if (press_button() == 1) {
			in.push(i);
			T++;
	    } else {
			move_outside(i);
		}
	}
	while (!in.empty()) {
		move_outside(in.top());
		in.pop();
	}
	
	int K = 0;
	int l = 0, r = N / T + 1;
	while (r - l > 1) {
		int m = (l + r) / 2;
		if (check(m, K)) {
			l = m;
		} else {
			r = m;
		}
	}
	
	return l;
}

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