Submission #774573

#	Time	Username	Problem	Language	Result	Execution time	Memory
774573		GusterGoose27	Rarest Insects (IOI22_insects)	C++17	64.45 / 100	132 ms	568 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() <= r-l) return 1;
	if (l == r) {
		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);
}

Compilation message (stderr)

insects.cpp: In function 'int solve(int, int, std::vector<int>&, std::vector<int>&)':
insects.cpp:11:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |  if (ex.size() <= r-l) return 1;
      |      ~~~~~~~~~~^~~~~~

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