Submission #815222

#	Time	Username	Problem	Language	Result	Execution time	Memory
815222		biank	Rarest Insects (IOI22_insects)	C++17	0 / 100	0 ms	208 KiB

insects

#include <bits/stdc++.h>

using namespace std;

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 = 0;
	for (int i=1; i<N; i++) {
		move_inside(i);
		int p = press_button();
		if (p == 1) {
			done[i] = true;
			in.push(i);
			T++;
		} else {
			move_outside(i);
		}
	}
	
	int ans = 1;
	
	while (true) {
		int K = 0;
		bool b = 0;
		while (!in.empty()) {
			move_outside(in.top());
			in.pop();
		}
		
		for (int i=0; i<N; i++) {
			if (done[i]) {
				continue;
			}
			
			b = 1;
			
			move_inside(i);
			int p = press_button();
			if (p == 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: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75