제출 #774568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774568		GusterGoose27	드문 곤충 (IOI22_insects)	C++17	0 / 100	88 ms	324 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
bool skip[MAXN];

int solve(int l, int r, vector<int> &reps, vector<int> &ex) { // also move all outside
	if (ex.size() < reps.size()) return 1;
	if (l == r) {
		move_outside(reps[l]);
		return ex.size()+1;
	}
	int mid = (l+r)/2;
	for (int i = mid+1; i <= r; i++) move_outside(reps[i]);
	vector<int> lex, rex;
	for (int v: ex) {
		move_inside(v);
		if (press_button() > 1) {
			lex.push_back(v);
		}
		else rex.push_back(v);
		move_outside(v);
	}
	int a = solve(l, mid, reps, lex);
	if (a == 1) return 1;
	for (int i = mid+1; i <= r; i++) move_inside(reps[i]);
	return min(a, solve(mid+1, r, reps, rex));
}

int min_cardinality(int n) {
    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);
    mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 1; i < n; i++) swap(perm[i], perm[gen()%(i+1)]);
	vector<int> reps;
	vector<int> extra;
	for (int i = 0; i < n; i++) {
		move_inside(perm[i]);
		if (press_button() > 1) {
			move_outside(perm[i]);
			extra.push_back(perm[i]);
		}
		else {
			skip[i] = 1;
			reps.push_back(perm[i]);
		}
	}
	return solve(0, reps.size()-1, reps, extra);
}

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