Submission #1062868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062868		Arapak	Rarest Insects (IOI22_insects)	C++17	37.53 / 100	136 ms	988 KiB

insects

#include "insects.h"
#include "bits/stdc++.h"

using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p) {
	return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto& os, const auto &v) {
	os<<"{";
	for(auto it=begin(v);it!=end(v);++it) {
		if(it != begin(v)) os<<", ";
		os<<(*it);
	}
	return os<<"}";
}

void dbg_out(auto... x) {
	((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

int n;
vi perm;
vi added;

void in(int i) {
	if(added[i]) return;
	added[i] = true;
	move_inside(perm[i]);
}
void out(int i) {
	if(!added[i]) return;
	added[i] = false;
	move_outside(perm[i]);
}

int button() {
	int res = press_button();
	dbg(added, res);
	return res;
}

vi dsu, siz;
int find(int x) {
	if(dsu[x] == x) return x;
	return dsu[x] = find(dsu[x]);
}

void merge(int a, int b) {
	dbg("merge", a, b);
	a = find(a); b = find(b);
	if(a == b) return;
	if(siz[a] < siz[b]) swap(a, b);
	siz[a] += siz[b];
	dsu[b] = a;
}

vi merge_dsu(vi a, vi b) {
	if(sz(a) < sz(b)) swap(a, b);

	vector<tuple<int,int,int>> bin;

	for(auto x : a) in(x);
	rep(i,0,sz(b)) {
		in(b[i]);
		if(button() != 1) {
			bin.emplace_back(0,sz(a)-1,i);
		}
		out(b[i]);
	}

	while(!bin.empty()) {
		sort(all(bin));
		pii last = {-1, -1};
		vector<tuple<int,int,int>> new_bin;
		for(auto [l,r,ind] : bin) {
			dbg(l, r, ind);
			if(l == r) {
				merge(a[l], b[ind]);
				continue;
			}
			int mid = (l + r + 1) / 2;
			if(make_pair(l, r) != last) {
				rep(i,0,sz(a)) {
					if(l <= i && i < mid) in(a[i]);
					else out(a[i]);
				}
				last = {l, r};
			}
			in(b[ind]);
			if(button() == 1)
				l = mid;
			else
				r = mid - 1;
			out(b[ind]);
			new_bin.emplace_back(l, r, ind);
		}
		bin = new_bin;
	}
	rep(i,0,sz(a))
		out(a[i]);
	set<int> s;
	rep(i,0,sz(a)) s.insert(find(a[i]));
	rep(i,0,sz(b)) s.insert(find(b[i]));
	dbg(a, b, s);
	return vi(all(s));
}

vi solve(int l, int r) {
	if(l == r) return {l};
	int mid = (l + r) / 2;
	auto a = solve(l, mid);
	auto b = solve(mid+1, r);
	auto res = merge_dsu(a, b);
	dbg(l, r, res);
	return res;
}

int min_cardinality(int N) {
	n = N;
	perm.resize(n);
	iota(all(perm), 0);
	// random_shuffle(all(perm));
	added.assign(n, 0);
	siz.assign(n, 1);
	dsu.resize(n);
	iota(all(dsu), 0);
	solve(0, n-1);
	dbg(dsu);
	dbg(siz);
	int mini = n;
	rep(i,0,n)
		mini = min(mini, siz[find(i)]);
	return mini;
}

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