Submission #631842

#	Time	Username	Problem	Language	Result	Execution time	Memory
631842		jwvg0425	Rarest Insects (IOI22_insects)	C++17	100 / 100	60 ms	560 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)
{
	// i번 원소는 각 집합에서 l[i]번째 이상 r[i]번째 이하 원소임(맨왼쪽부터 그 집합 순서대로 다 포함시켰을때)
	vector<int> l(n, 1);
	vector<int> r(n, n);

	set<int> sel;

	for (int i = 0; i < n; i++)
	{
		move_inside(i);
		if (press_button() > 1)
		{
			l[i] = 2;
			move_outside(i);
			continue;
		}

		r[i] = 1;
		sel.insert(i);
	}

	int group = sel.size();

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

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

		set<int> noSel;

		for (auto& si : sel)
		{
			if (r[si] > mid)
				noSel.insert(si);
		}

		for (auto& no : noSel)
		{
			move_outside(no);
			sel.erase(no);
		}

		now = press_button();

		for (int i = 0; i < n; i++)
		{
			if (sel.find(i) != sel.end() || l[i] > mid)
				continue;

			move_inside(i);

			int x = press_button();
			if (x > mid)
			{
				l[i] = x;
				move_outside(i);
				continue;
			}

			sel.insert(i);
			if (x > now)
			{
				l[i] = r[i] = x;
				now = x;
			}
			else
			{
				// 최소한 now번째 이하임
				r[i] = min(r[i], now);
			}
		}

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

	return ans;
}

Compilation message (stderr)

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

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