Submission #631628

#	Time	Username	Problem	Language	Result	Execution time	Memory
631628		jwvg0425	Rarest Insects (IOI22_insects)	C++17	50 / 100	212 ms	464 KiB

insects

#include "insects.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int min_cardinality(int n)
{
	int group = 1;
	int two = 0;

	move_inside(0);
	set<int> sel = { 0, };
	for (int i = 1; i < n; i++)
	{
		move_inside(i);
		if (press_button() > 1)
		{
			two++;
			move_outside(i);
			continue;
		}

		sel.insert(i);
		group++;
	}

	if (two < group)
		return 1;

	if (group == 1)
		return n;

	int lo = 1, hi = n / group;
	int ans = n;

	int sz = 1;

	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;

		if (sz < mid)
		{
			for (int i = 0; i < n; i++)
			{
				if (sel.find(i) != sel.end())
					continue;

				move_inside(i);
				int now = press_button();
				if (now > mid)
				{
					move_outside(i);
					continue;
				}

				sz = now;
				sel.insert(i);
			}
		}
		else if(sz > mid)
		{
			for (auto& si : sel)
				move_outside(si);
			sel.clear();

			for (int i = 0; i < n; i++)
			{
				move_inside(i);
				if (press_button() > mid)
				{
					move_outside(i);
					continue;
				}

				sel.insert(i);
			}
		}

		if (sel.size() == mid * group)
		{
			ans = mid;
			lo = mid + 1;
		}
		else
		{
			hi = mid - 1;
		}
	}

	return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:104:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |   if (sel.size() == mid * group)
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~

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