Submission #1060138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060138		parsadox2	Rarest Insects (IOI22_insects)	C++17	10 / 100	245 ms	596 KiB

insects

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

using namespace std;

const int N = 2e3 + 10 , Lg = 10;
int n , ans;
bool bad[N] , dead[N];

bool check(int mid)
{
	int all = 0;
	for(int i = 0 ; i < n ; i++)  if(!dead[i])
	{
		bad[i] = false;
		all++;
		move_inside(i);
		int val = press_button();
		if(val > mid)
		{
			bad[i] = true;
			move_outside(i);
		}
	}
	for(int i = 0 ; i < n ; i++)  if(!bad[i] && !dead[i])
		move_outside(i);
	bool flg = true;
	vector <int> vec;
	int cnt = 0;
	for(int i = 0 ; i < n ; i++)  if(bad[i] && !dead[i])
	{
		flg = false;
		move_inside(i);
		int val = press_button();
		if(val > 1)
		{
			move_outside(i);
			cnt++;
		}
		else
		{
			cnt += (mid + 1);
			vec.push_back(i);
		}
	}
	for(auto u : vec)
	{
		move_outside(u);
	}
	//cout << mid << " : " << cnt << " " << all << endl;
	if(cnt == all)
	{
		for(int i = 0 ; i < n ; i++)  if(!dead[i] && !bad[i])
			dead[i] = true;
		return false;
	}
	for(int i = 0 ; i < n ; i++)  if(bad[i] && !dead[i])
		dead[i] = true;
	return true;
}

int min_cardinality(int nn)
{
	n = nn;
	while(!check(1))
	{
		ans++;
	}
	return ans + 1;
}

Compilation message (stderr)

insects.cpp: In function 'bool check(int)':
insects.cpp:27:7: warning: variable 'flg' set but not used [-Wunused-but-set-variable]
   27 |  bool flg = true;
      |       ^~~

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