Submission #776554

#	Time	Username	Problem	Language	Result	Execution time	Memory
776554		SanguineChameleon	Rarest Insects (IOI22_insects)	C++17	61.85 / 100	144 ms	456 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;
vector<int> cnt;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

void solve(int lt, int rt, vector<int> rem, bool on) {
	if (lt == rt) {
		cnt[lt] += (int)rem.size();
		return;
	}
	if (rem.empty()) {
		return;
	}
	int mt = (lt + rt) / 2;
	if (on) {
		for (int i = mt + 1; i <= rt; i++) {
			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);
		}
		solve(lt, mt, left_rem, true);
		solve(mt + 1, rt, right_rem, false);
	}
	else {
		for (int i = mt + 1; i <= rt; i++) {
			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);
		}
		solve(lt, mt, left_rem, false);
		solve(mt + 1, rt, right_rem, true);
	}
}

int min_cardinality(int N) {
	for (int i = 0; i < N; i++) {
		order[i] = i;
	}
	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]);
		}
	}
	cnt.resize(diff.size(), 1);
	solve(0, (int)diff.size() - 1, rem, true);
	int res = N + 1;
	for (auto x: cnt) {
		res = min(res, x);
	}
	return res;
}

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