Submission #837170

#	Time	Username	Problem	Language	Result	Execution time	Memory
837170		ymm	Rarest Insects (IOI22_insects)	C++17	100 / 100	52 ms	440 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

#define in move_inside
#define out move_outside
#define get press_button

pair<vector<int>, vector<int>> split(vector<int> vec, int k)
{
	vector<int> vec1, vec2;
	for (int x : vec) {
		in(x);
		if (get() > k) {
			out(x);
			vec2.push_back(x);
		} else {
			vec1.push_back(x);
		}
	}
	for (int x : vec1)
		out(x);
	return {vec1, vec2};
}

int dc(vector<int> vec, int cnt)
{
	if (vec.size() < cnt)
		return 0;
	int k = (vec.size()+2*cnt-1)/(2*cnt);
	auto [v1, v2] = split(vec, k);
	if (v1.size() < cnt * k)
		return dc(v1, cnt);
	else
		return k + dc(v2, cnt);
}

int min_cardinality(int N) {
	vector<int> vec(N);
	iota(vec.begin(), vec.end(), 0);
	auto [v1, v2] = split(vec, 1);
	int cnt = v1.size();
	if (cnt == 1)
		return N;
	return 1 + dc(v2, cnt);
}

Compilation message (stderr)

insects.cpp: In function 'int dc(std::vector<int>, int)':
insects.cpp:30:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  if (vec.size() < cnt)
      |      ~~~~~~~~~~~^~~~~
insects.cpp:34:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |  if (v1.size() < cnt * k)
      |      ~~~~~~~~~~^~~~~~~~~

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