제출 #1063123

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1063123		Arapak	드문 곤충 (IOI22_insects)	C++17	99.77 / 100	42 ms	696 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 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;
	dbg(ind);
	int t = 0;
	int b = 0, e = n / k + 1;
	while(b < e) {
		int mid = (b + e + 1) / 2;
		auto [poss, vals] = check(mid - t);
		if(poss) {
			b = mid;
			for(auto x : vals)
				removed[x] = true;
			t = mid;
		}
		else {
			e = mid - 1;
			fill(all(removed), true);
			for(auto x : vals)
				removed[x] = false;
		}
	}
	return b + 1;
}

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