Submission #631512

#	Time	Username	Problem	Language	Result	Execution time	Memory
631512		jwvg0425	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	198 ms	440 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;

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

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

	for (auto& si : sel)
		move_outside(si);

	sel.clear();

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

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

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

			sel.push_back(i);
		}

		int sz = sel.size();

		for (auto& si : sel)
			move_outside(si);

		sel.clear();

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

	return ans;
}

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