Submission #630643

#	Time	Username	Problem	Language	Result	Execution time	Memory
630643		errorgorn	Rarest Insects (IOI22_insects)	C++17	100 / 100	61 ms	444 KiB

insects

#include "insects.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
#define in move_inside
#define out move_outside
#define get press_button
 
signed min_cardinality(signed n) {
	int num=0;
 
	vector<int> v,rem;
	rep(x,0,n){
		in(x);
		if (get()==2){
			rem.pub(x);
			out(x);
		}
		else{
			v.pub(x);
			num++;
		}
	}
	for (auto it:v) out(it);
	v.clear();
 
	int ans=1;
	while (true){
		int best=1e9;
		int h=-1;
		rep(x,1,sz(rem)/num+1){
			int temp=max(num*x-1,sz(rem)-num*x);
			if (temp<best){
				best=temp;
				h=x;
			}
		}
 
		if (h==-1) break;
 		
		vector<int> small,big;
		vector<int> v;
		
		int oth=sz(rem);
		
		shuffle(all(rem),rng);
		
		for (auto it:rem){
			if (sz(small)==h*num){
				big.pub(it);
			}
			else{
				in(it);
				if (get()==h+1){
					big.pub(it);
					out(it);
				}
				else{
					small.pub(it);
					v.pub(it);
				}
			}
			
			oth--;
		}
 
		//cout<<sz(small)<<" "<<sz(big)<<endl;
		if (sz(small)==h*num){
			ans+=h;
			rem=big;
		}
		else{
			rem=small;
		}
 
		for (auto it:v) out(it);
	}
 
	return ans;
}

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