Submission #774583

#	Time	Username	Problem	Language	Result	Execution time	Memory
774583		GusterGoose27	Rarest Insects (IOI22_insects)	C++17	65.25 / 100	130 ms	484 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
bool active[MAXN];
int inv[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;
	if (active[l]) for (int i = mid+1; i <= r; i++) {
		move_outside(reps[i]);
		active[i] = 0;
	}
	else for (int i = l; i <= mid; i++) {
		move_inside(reps[i]);
		active[i] = 1;
	}
	vector<int> lex, rex;
	for (int v: ex) {
		if (inv[v] < inv[reps[mid+1]]) {
			lex.push_back(v);
			continue;
		}
		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;
	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)]);
    for (int i = 0; i < n; i++) inv[perm[i]] = i;
	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 {
			active[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:12:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |  if (ex.size() <= r-l) return 1;
      |      ~~~~~~~~~~^~~~~~

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