Submission #631655

#	Time	Username	Problem	Language	Result	Execution time	Memory
631655		jwvg0425	Rarest Insects (IOI22_insects)	C++17	50.03 / 100	205 ms	1244 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;

	map<int, set<int>> stateByMid;

	stateByMid[now] = sel;

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

		if (now > mid)
		{
			auto x = (--stateByMid.lower_bound(mid))->yy;

			for (auto& s : sel)
			{
				if (x.find(s) != x.end())
					continue;

				move_outside(s);
			}

			sel = x;
		}

		for (int i = 0; i < n; i++)
		{
			if (sel.find(i) != sel.end())
				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] = now;
			}
		}

		stateByMid[mid] = sel;

		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:110:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |   if (sel.size() == group * mid)
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~

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