Submission #837154

#	Time	Username	Problem	Language	Result	Execution time	Memory
837154		biank	Rarest Insects (IOI22_insects)	C++17	100 / 100	46 ms	712 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();

stack <int> in;
set <int> s;
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(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 = old_k;
	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, l = 0, r = N/T+1;
	
	while (l+1 < r) {
		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