Submission #956141

#	Time	Username	Problem	Language	Result	Execution time	Memory
956141		n1k	Rarest Insects (IOI22_insects)	C++17	61.06 / 100	91 ms	1688 KiB

insects

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

using namespace std;

const int LOG = 12;
int n;

vector<set<int>> active(LOG);
vector<int> v;

void build(int lb, int rb, int level){
	if(lb>=rb) return;
	int mb = (lb + rb) / 2;
	for(int i=lb; i<=mb; i++){
		active[level].insert(v[i]);
	}
	build(lb, mb, level+1);
	build(mb+1, rb, level+1);

}

int min_cardinality(int N) {
	n = N;

	vector<int> rest;

	for(int i=0; i<n; i++){
		move_inside(i);
		v.push_back(i);
		if(press_button()>=2){
			move_outside(i);
			v.pop_back();
			rest.push_back(i);
		}
	}

	build(0, v.size()-1, 0);
	int m=n-v.size();

	vector<int> lb(m), rb(m, v.size()-1), count(v.size(), 1);
	set<int> cur(v.begin(), v.end());

	for(int level=0; level<LOG; level++){
		// activate
		for(auto x:active[level]){
			if(not cur.count(x)){
				cur.insert(x);
				move_inside(x);
			}
		}
		auto c_cur=cur;;
		// deactivate
		for(auto x:c_cur){
			if(not active[level].count(x)){
				cur.extract(x);
				move_outside(x);
			}
		}
		// query
		for(int i=0; i<m; i++){
			if(lb[i]>=rb[i]) continue;
			int mb = (lb[i] + rb[i])/2;
			move_inside(rest[i]);
			if(press_button()==2){
				rb[i]=mb;
			}else{
				lb[i]=mb+1;
			}
			move_outside(rest[i]);
		}
	}

	for(int i=0; i<m; i++){
		count[lb[i]]++;
	}

	return *min_element(count.begin(), count.end());
}

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