Submission #815361

#	Time	Username	Problem	Language	Result	Execution time	Memory
815361		biank	Rarest Insects (IOI22_insects)	C++17	90.51 / 100	112 ms	324 KiB

insects

#include <bits/stdc++.h>

using namespace std;

#define ALL(x) x.begin(), x.end()

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

int min_cardinality(int N) {
	vector <bool> done(N, 0);
	stack <int> in;
	move_inside(0);
	done[0] = true;
	in.push(0);
	int T = 1;
	for (int i=1; i<N; i++) {
		move_inside(i);
		if (press_button() == 1) {
			done[i] = true;
			in.push(i);
			T++;
		} else {
			move_outside(i);
		}
	}
	
	int ans = 1;
	vector <int> p(N);
	for (int i=0; i<N; i++) {
		p[i] = i;
	}
	while (true) {
		random_shuffle(ALL(p));
		int K = 0;
		bool b = 0;
		while (!in.empty()) {
			move_outside(in.top());
			in.pop();
		}
		
		for (int i:p) {
			if (done[i]) {
				continue;
			}
			
			b = 1;
			
			move_inside(i);
			if (press_button() == 1) {
				done[i] = true;
				in.push(i);
				K++;
			} else {
				move_outside(i);
			}
			
			if (K == T) {
				break;
			}
		}
		
		if (K < T || !b) {
			break;
		}
		
		ans++;
	}
	
	return ans;
}

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