Submission #776672

#	Time	Username	Problem	Language	Result	Execution time	Memory
776672		SanguineChameleon	Rarest Insects (IOI22_insects)	C++17	65.56 / 100	122 ms	440 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 res;

struct state {
	int lt, rt;
	vector<int> rem;
	bool on;

	state() {};

	state(int _lt, int _rt, vector<int> _rem, bool _on): lt(_lt), rt(_rt), rem(_rem), on(_on) {};
};

bool operator<(state S1, state S2) {
	return S1.rem.size() > S2.rem.size();
}

priority_queue<state> Q;

void solve(int lt, int rt, vector<int> rem, bool on) {
	if (res == 1) {
		return;
	}
	if (lt == rt) {
		res = min(res, (int)rem.size() + 1);
		return;
	}
	if (rem.empty()) {
		res = 1;
		return;
	}
	int mt = (lt + rt) / 2;
	bool all_left = true;
	for (auto x: rem) {
		all_left &= (pref[x] <= mt);
	}
	if (all_left) {
		res = 1;
		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);
		}
		Q.emplace(lt, mt, left_rem, true);
		Q.emplace(mt + 1, rt, right_rem, false);
	}
	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);
		}
		Q.emplace(lt, mt, left_rem, false);
		Q.emplace(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]);
		}
	}
	res = N + 1;
	Q.emplace(0, (int)diff.size() - 1, rem, true);
	while (!Q.empty()) {
		int lt = Q.top().lt;
		int rt = Q.top().rt;
		rem = Q.top().rem;
		bool on = Q.top().on;
		Q.pop();
		solve(lt, rt, rem, on);
	}
	return res;
}

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