Submission #776650

#	Time	Username	Problem	Language	Result	Execution time	Memory
776650		SanguineChameleon	Rarest Insects (IOI22_insects)	C++17	25 / 100	57 ms	328 KiB

insects

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

const int maxN = 2e3 + 20;
int order[maxN];
int pref[maxN];
vector<int> diff;
mt19937 gen(69420);
int mi;

void solve(int lt, int rt, vector<int> rem, bool on) {
	if (mi == 1) {
		return;
	}
	if (lt == rt) {
		mi = min(mi, (int)rem.size() + 1);
		return;
	}
	if (rem.empty()) {
		mi = 1;
		return;
	}
	int mt = (lt + rt) / 2;
	bool all_left = true;
	for (auto x: rem) {
		all_left &= (pref[x] <= mt);
	}
	if (all_left) {
		solve(lt, mt, rem, on);
		return;
	}
	if (on) {
		for (int i = mt + 1; i <= rt; i++) {
			if (diff[i] == -1) {
				continue;
			}
			move_outside(diff[i]);
		}
		vector<int> left_rem;
		vector<int> right_rem;
		for (auto x: rem) {
			if (pref[x] <= mt) {
				left_rem.push_back(x);
				continue;
			}
			move_inside(x);
			if (press_button() == 2) {
				left_rem.push_back(x);
			}
			else {
				right_rem.push_back(x);
			}
			move_outside(x);
		}
		if (left_rem.size() < right_rem.size()) {
			solve(lt, mt, left_rem, true);
			solve(mt + 1, rt, right_rem, false);
		}
		else {
			solve(mt + 1, rt, right_rem, false);
			solve(lt, mt, left_rem, true);
		}
	}
	else {
		for (int i = mt + 1; i <= rt; i++) {
			if (diff[i] == -1) {
				continue;
			}
			move_inside(diff[i]);
		}
		vector<int> left_rem;
		vector<int> right_rem;
		for (auto x: rem) {
			if (pref[x] <= mt) {
				left_rem.push_back(x);
				continue;
			}
			move_inside(x);
			if (press_button() == 2) {
				right_rem.push_back(x);
			}
			else {
				left_rem.push_back(x);
			}
			move_outside(x);
		}
		if (left_rem.size() < right_rem.size()) {
			solve(lt, mt, left_rem, false);
			solve(mt + 1, rt, right_rem, true);
		}
		else {
			solve(mt + 1, rt, right_rem, true);
			solve(lt, mt, left_rem, false);
		}
	}
}

int min_cardinality(int N) {
	for (int i = 0; i < N; i++) {
		order[i] = i;
	}
	reverse(order, order + N);
	shuffle(order, order + N, gen);
	diff.push_back(order[0]);
	move_inside(order[0]);
	vector<int> rem;
	for (int i = 1; i < N; i++) {
		move_inside(order[i]);
		if (press_button() == 1) {
			diff.push_back(order[i]);
		}
		else {
			pref[order[i]] = (int)diff.size() - 1;
			rem.push_back(order[i]);
			move_outside(order[i]);
		}
	}
	mi = N / (int)diff.size();
	solve(0, (int)diff.size() - 1, rem, true);
	return mi;
}

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