Submission #628512

#	Time	Username	Problem	Language	Result	Execution time	Memory
628512		Gullesnuffs	Rarest Insects (IOI22_insects)	C++17	93.25 / 100	92 ms	436 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);
	vector<int> added;
	while (res.num_tried < max_tried) {
		int x = remaining.front();
		//cerr << "Checking " << x << endl;
		remaining.pop_front();
		++res.num_tried;
		move_inside(x);
		//cerr << "press_button = " << press_button() << endl;
		if (press_button() <= target_h) {
			added.push_back(x);
			//cerr << "Accepted" << endl;
			++res.num_added;
			res.done_after = res.num_tried;
			if (res.num_added == num_different * (target_h-old_h)) {
				return res;
			}
		} else {
			//cerr << "Rejected" << endl;
			remaining.push_back(x);
			move_outside(x);
		}
	}
	if (old_h != 0) {
		for (int x : added) {
			remaining.push_front(x);
			move_outside(x);
			//cerr << "Remove " << x << endl;
		}
	}
	return res;
}

double fac(int n, int k) {
	return n*log(n)-k*log(k)-(n-k)*log(n-k);
}

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);
	deque<int> tmp = remaining;
	remaining = deque<int>();
	while (sz(tmp) > 0) {
		remaining.push_back(tmp.front());
		tmp.pop_front();
	}
	int num_different = res.num_added;
	int h = 1;
	int max_h = N/num_different;
	int L = res.done_after;
	double C = -10.0;
	while (h < max_h) {
		int new_h = h+1;
		if (L > 0) {
			if (L < N) {
				new_h = max(new_h, (int)(h+(N-L)/(L+0.0)*(h-1)));
			} else {
				new_h = max(new_h, (int)(h+(N-h*num_different)/(L+0.0)*(h-1)));
				new_h = min(new_h, (h+max_h+1)/2);
				assert(max_h > h);
				assert(new_h != h);
			}
			/*int k = 1;
			while (true) {
				//double p = (h+k)*log(h+k)-h*log(h)-k*log(k)+h*log(L/(N+0.0))+k*log((N-L)/(N+0.0));
				cerr << fac(L, h) << endl;
				cerr << fac(N-L, k) << endl;
				cerr << fac(N, h+k) << endl;
				double p = fac(L, h)+fac(N-L, k)-fac(N, h+k);
				cerr << "k = " << k << ", p = " << p << endl;
				if (p < C-log(N)) {
					k++;
				} else {
					break;
				}
			}
			cerr << "h = " << h << endl;
			cerr << "L = " << L << endl;
			cerr << "N = " << N << endl;
			cerr << "k = " << k << endl;
			if (k > 2) {
				new_h = h + floor(k);
			}*/
		}
		res = check(remaining, h, new_h, num_different);
		L += res.done_after;
		cerr << "num_added = " << res.num_added << endl;
		if (res.num_added < num_different * (new_h - h)) {
			max_h = min(max_h, new_h-1);
		} else {
			h = new_h;
		}
	}
	return 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)) {
      |      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:82:9: warning: unused variable 'C' [-Wunused-variable]
   82 |  double C = -10.0;
      |         ^

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