Submission #956906

#	Time	Username	Problem	Language	Result	Execution time	Memory
956906		n1k	드문 곤충 (IOI22_insects)	C++17	53.16 / 100	94 ms	1460 KiB

insects

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

using namespace std;

int n;

int min_cardinality(int N) {
	n = N;

	vector<int> v;
	set<int> in, out;

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

	mt19937 mt(4732012);
	int lb = 0, rb = n / v.size();
	while(lb<rb){
		int mb = (lb+rb+1)/2;

		vector<int> order(out.begin(), out.end()), last;
		shuffle(order.begin(), order.end(), mt);

		for(auto x:order){
			if(v.size()*mb==in.size())
				break;

			out.extract(x);
			in.insert(x);
			last.push_back(x);
			move_inside(x);

			if(press_button()>mb+1){
				move_outside(x);
				in.extract(x);
				out.insert(x);
				last.pop_back();
			}
		}

		if(v.size()*mb==in.size()){
			lb=mb;
		}else{
			rb=mb-1;
			for(auto x:last){
				move_outside(x);
				in.extract(x);
				out.insert(x);
			}
		}
	}

	return lb+1;
}

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