Submission #1240979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240979		ansori	Rarest Insects (IOI22_insects)	C++20	99.95 / 100	25 ms	472 KiB

insects

#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int n){
	long long x = rng();
	return abs(x) % n + 1;
}
vector<int> ps;
int n , dst;
void move_inside(int i);
void push(int i){
	int p = -1; 
	for(int j = 0;j < ps.size(); ++ j) if(ps[j] == i) p = j;
	if(p != -1) return ;
	move_inside(i);
	ps.push_back(i);
}
void move_outside(int i);
void remove(int i){
	int p = -1; 
	for(int j = 0;j < ps.size(); ++ j) if(ps[j] == i) p = j;
	if(p == -1) return ;
	move_outside(i);
	ps.erase(ps.begin() + p , ps.begin() + p + 1);
}
int press_button();
int press() {return press_button(); }

int min_cardinality(int N){
	n = N;
	vector<int> v , ls;
	bool pre = true;
	for(int i = 0;i < n; ++ i){
		push(i);
		v.push_back(i);
		if(i and press() > 1) remove(i);
	}
	int ds = ps.size() ;
	for(int i = 0;i < ps.size(); ++ i) swap(ps[i] , ps[rand(ds) - 1]);
	//for(auto to : ps) cout << to << ' ';
	ls = ps;
	if(ds == 1) return n;
	int l = 1;
	int r = n / ds + 1;
	while(l + 1 < r){
		int mid = (l + r) / 2;
		if(! pre){
			for(auto to : v){
				bool w = false;
				for(auto it : ls) if(to == it) w = true;
				if(! w) remove(to);
			}
		}
		for(int i = 0;i < v.size(); ++ i){
			int sz = ps.size();
			if(sz == ds * mid) break;
			push(v[i]);
			if(sz != ps.size() and press() > mid) remove(v[i]);
		}
		if(ps.size() == ds * mid){
			l = mid;
			ls = ps;
			pre = true;
		}
		else{
			r = mid;
			v = ps;
			pre = false;
		}
	}
	ps.clear();
	return l;
}

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