Submission #628397

#	Time	Username	Problem	Language	Result	Execution time	Memory
628397		Gullesnuffs	Rarest Insects (IOI22_insects)	C++17	68.02 / 100	279 ms	764 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;

struct Result {
	int num_added;
	int done_after;
	int num_tried;
};

Result check(deque<int>& remaining, int old_h, int target_h, int num_different) {
	cerr << "Running with target_h = " << target_h << endl;
	Result res;
	res.num_added = 0;
	res.done_after = 0;
	res.num_tried = 0;
	if (remaining.size() < num_different*(target_h-old_h)) {
		return res;
	}
	int max_tried = sz(remaining);
	while (res.num_tried < max_tried) {
		int x = remaining.front();
		cerr << "Checking " << x << endl;
		remaining.pop_front();
		++res.num_tried;
		move_inside(x);
		if (press_button() <= target_h) {
			cerr << "Accepted" << endl;
			++res.num_added;
			res.done_after = res.num_tried;
			if (res.num_added == num_different * (target_h-old_h)) {
				break;
			}
		} else {
			cerr << "Rejected" << endl;
			remaining.push_back(x);
			move_outside(x);
		}
	}
	return res;
}

int min_cardinality(int N) {
	vector<int> v;
	rep(i,0,N)
		v.push_back(i);
	deque<int> remaining;
	for (int x : v)
		remaining.push_back(x);
	random_shuffle(all(remaining));
	auto res = check(remaining, 0, 1, N);
	int num_different = res.num_added;
	int h = 1;
	while (true) {
		res = check(remaining, h, h+1, num_different);
		if (res.num_added < num_different) {
			return h;
		}
		h++;
	}
}

Compilation message (stderr)

insects.cpp: In function 'Result check(std::deque<int>&, int, int, int)':
insects.cpp:23:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |  if (remaining.size() < num_different*(target_h-old_h)) {
      |      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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