Submission #1063149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063149		Arapak	Rarest Insects (IOI22_insects)	C++17	99.77 / 100	46 ms	600 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 get_k() {
	vi res;
	rep(i,0,n) {
		in(i);
		if(button() > 1)
			out(i);
		else res.push_back(i);
	}
	rep(i,0,n) out(i);
	return res;
}

int k;
vector<bool> removed;

pair<bool, vi> check(int x) {
	rep(i,0,n) {
		if(removed[i]) continue;
		in(i);
		if(button() > x) out(i);
	}
	vi vals;
	rep(i,0,n)
		if(added[i]) vals.push_back(i);
	rep(i,0,n) out(i);
	return {sz(vals) == k*x, vals};
}

int t = 0;

bool solve(int v) {
	auto [poss, vals] = check(v - t);
	if(poss) {
		for(auto x : vals)
			removed[x] = true;
		t = v;
	}
	else {
		fill(all(removed), true);
		for(auto x : vals)
			removed[x] = false;
	}
	return poss;
}

int min_cardinality(int N) {
	n = N;
	perm.resize(n);
	iota(all(perm), 0);
	random_shuffle(all(perm));
	added.assign(n, 0);
	vi ind = get_k();
	k = sz(ind);
	removed.assign(n, 0);
	for(auto i : ind)
		removed[i] = true;

	if(k*5 > n) {
		if(solve(3)) return 4;
		if(solve(2)) return 3;
		if(solve(1)) return 2;
		return 1;
	}

	dbg(ind);
	int t = 0;
	int b = 0, e = (n - 1) / k;
	while(b < e) {
		int mid = (b + e + 1) / 2;
		if(solve(mid)) b = mid;
		else e = mid - 1;
	}
	return b + 1;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:120:6: warning: unused variable 't' [-Wunused-variable]
  120 |  int t = 0;
      |      ^

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