Submission #1063457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063457		parsadox2	Rarest Insects (IOI22_insects)	C++17	99.56 / 100	43 ms	852 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
 
using namespace std;
 
const int N = 2e3 + 10 , Lg = 10;
int n , ans , cnt;
bool bad[N] , dead[N];
 
bool check(int mid)
{
	//cout << "Check : " << mid << endl;
	int all_in = 0;
	for(int i = 0 ; i < n ; i++)  if(!dead[i])
	{
		bad[i] = false;
		all_in++;
		move_inside(i);
		int val = press_button();
		if(val > mid)
		{
			bad[i] = true;
			all_in--;
			move_outside(i);
		}
	}
	//cout << mid << " : " << all_in << endl;
	for(int i = 0 ; i < n ; i++)  if(!bad[i] && !dead[i])
		move_outside(i);
	if(all_in == cnt * mid)
	{
		for(int i = 0 ; i < n ; i++)  if(!dead[i] && !bad[i])
			dead[i] = true;
		return true;
	}
	else
	{
		for(int i = 0 ; i < n ; i++)  if(!dead[i] && bad[i])
			dead[i] = true;
		return false;
	}
}
 
int min_cardinality(int nn)
{
	n = nn;
	vector <int> vec;
	for(int i = 0 ; i < n ; i++)
	{
		move_inside(i);
		int val = press_button();
		if(val == 1)
		{
			cnt++;
			vec.push_back(i);
		}
		else
		{
			move_outside(i);
		}
	}
	for(auto u : vec)
		move_outside(u);
	//cout << cnt << endl;
	int mx = n / cnt + 1;
	while(mx > 1)
	{
		int mid = mx / 2;
		//cout << mx << " : " << mid << endl;
		if(check(mid))
		{
			mx = mx - mid;
			ans += mid;
		}
		else
		{
			mx = mid;
		}
	}
	return ans;
}

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