Submission #776867

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

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

int D;

int solve(int K, vector<int> rem, int off) {
	if (K == 0) {
		return 0;
	}
	int mid = (K + 1) / 2;
	vector<int> in, out;
	for (auto x: rem) {
		move_inside(x);
		if (press_button() > off + mid) {
			move_outside(x);
			out.push_back(x);
		}
		else {
			in.push_back(x);
		}
	}
	if (press_button() == D * (off + mid)) {
		return solve(K - mid, out, off + mid);
	}
	else {
		for (auto x: in) {
			move_outside(x);
		}
		return solve(mid - 1, rem, off);
	}
}

int min_cardinality(int N) {
	vector<int> rem;
	for (int i = 0; i < N; i++) {
		move_inside(i);
		if (press_button() == 2) {
			move_outside(i);
			rem.push_back(i);
		}
		else {
			D++;
		}
	}
	return 1 + solve(N / D - 1, rem, 1);
}

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