Submission #837143

#	Time	Username	Problem	Language	Result	Execution time	Memory
837143		biank	Rarest Insects (IOI22_insects)	C++17	49.02 / 100	182 ms	604 KiB

insects

#include <bits/stdc++.h>

using namespace std;

#define ALL(x) x.begin(), x.end()
#define DBGY(x) cerr << #x << ": " << x << ", ";
#define DBG(x) cerr << #x << ": " << x << endl;

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

set <int> s;
vector <int> in, out;
int T;

bool check(int m, int &K) {
	int old_k = K;
	vector <int> v(ALL(s));
	random_shuffle(ALL(v));
	for (int i:v) {
		move_inside(i);
		if (press_button() <= m) {
			in.push_back(i);
			if (++K < m*T) {
				continue;
			}
			for (int j:in) {
				s.erase(j);
			}
			return true;
		} else {
			out.push_back(i);
			move_outside(i);
		}
	}
	for (int j:in) {
		move_outside(j);
	}
	for (int j:out) {
		s.erase(j);
	}
	K = old_k;
	return false;
}

int min_cardinality(int N) {
	srand(time(0));
	move_inside(0);
	in.push_back(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_back(i);
			T++;
		} else {
			move_outside(i);
		}
	}
	for (int i:in) {
		move_outside(i);
	}
	
	int K = 0, l = 0, r = N+1;
	
	while (l+1 < r) {
		in.clear();
		out.clear();
		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: 24.02 / 75