Submission #1062769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062769		Arapak	Rarest Insects (IOI22_insects)	C++17	0 / 100	5 ms	344 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;
vector<bool> 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]);
}

vi siz;
vi ind;

void find(int index) {
	dbg(index);
	in(index);
	for(auto x : ind)
		in(x);
	if(press_button() == 1) {
		siz[index] = 1;
		ind.push_back(index);
		return;
	}
	int b = 0, e = sz(ind)-1;
	while(b < e) {
		int mid = (b + e) / 2;
		rep(i,b,mid) in(i); 
		rep(i,mid,e+1) out(i);
		dbg(b, e, mid);
		if(press_button() == 1)
			b = mid + 1;
		else
			e = mid;
	}
	siz[ind[b]]++;
	out(index);
}

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);
	siz[0] = 1;
	ind.push_back(0);
	rep(i,1,n) find(i);
	int mini = n;
	rep(i,0,n)
		if(siz[i] != -1)
			mini = min(mini, siz[i]);
	return mini;
}

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