Submission #629226

#	Time	Username	Problem	Language	Result	Execution time	Memory
629226		Gullesnuffs	Rarest Insects (IOI22_insects)	C++17	100 / 100	83 ms	1744 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;

vector<deque<int>> at_h;
vector<int> min_num_at_or_below_h;
vector<int> max_num_at_or_below_h;
int num_inside = 0;
vector<int> v;
int n;
int H = 1;
int h_lo;
int h_hi;
int target_h;
int num_move_inside = 0;
int num_queries = 0;

void debug() {
	cerr << endl << endl;
	rep(h,1,sz(at_h)) {
		if (!at_h[h].empty() || max_num_at_or_below_h[h]) {
			cerr << "h = " << h << ". Num at or below = " << min_num_at_or_below_h[h] << " - " << max_num_at_or_below_h[h]+num_inside << ". Insects = [";
			for (int x : at_h[h]) {
				cerr << x << ", ";
			}
			cerr << "]" << endl;
		}
	}
	cerr << "num_inside = " << num_inside << endl;
	cerr << "h_lo = " << h_lo << endl;
	cerr << "h_hi = " << h_hi << endl;
	cerr << "target_h = " << target_h << endl;
	cerr << "num_move_inside = " << num_move_inside << endl;
	cerr << "num_queries = " << num_queries << endl;
}

int press_button_cache = -1;
void _move_inside(int i) {
	++num_inside;
	++num_move_inside;
	press_button_cache = -1;
	move_inside(i);
}
void _move_outside(int i) {
	--num_inside;
	press_button_cache = -1;
	move_outside(i);
}
int cur_h() {
	if (press_button_cache == -1) {
		press_button_cache = press_button();
		++num_queries;
	}
	return press_button_cache;
}


int min_cardinality(int N) {
	srand(2);
	n = N;
	at_h.resize(N+3);
	min_num_at_or_below_h.resize(N+2);
	max_num_at_or_below_h.resize(N+2);
	rep(i,0,N)
		v.push_back(i);
	random_shuffle(all(v));
	deque<int> remaining;
	int last_added = 0;
	for (int x : v) {
		if (num_queries > N*0.99 && last_added < N/2) {
			++num_queries;
			remaining.push_front(x);
			continue;
		}
		_move_inside(x);
		if (cur_h() > 1) {
			_move_outside(x);
			remaining.push_front(x);
		} else {
			at_h[1].push_back(x);
			last_added = num_queries;
		}
	}
	vector<int> min_count_inside(N, 1);
	int num_different = num_inside;
	h_hi = N/num_different;
	h_lo = 1;
	if (num_different == 1) {
		h_lo = N;
	}
	target_h = h_lo+1;
	bool start_binary_search = false;
	bool initial_search = true;
	target_h = 3;
	while (h_lo < h_hi) {
		max_num_at_or_below_h[0] = 0;
		min_num_at_or_below_h[0] = 0;
		vector<int> tmp(N+2);
		for (int x : remaining) {
			tmp[min_count_inside[x]]++;
		}
		rep(i,1,h_hi+1) {
			min_num_at_or_below_h[i] = min_num_at_or_below_h[i-1] + sz(at_h[i]);
			max_num_at_or_below_h[i] = max_num_at_or_below_h[i-1] + tmp[i-1];
			if (max_num_at_or_below_h[i]+num_inside < i*num_different) {
				h_hi = min(h_hi, i-1);
			}
			if (min_num_at_or_below_h[i] >= i*num_different) {
				assert(min_num_at_or_below_h[i] == i*num_different);
				h_lo = max(h_lo, i);
			}
		}
		h_lo = max(h_lo, H-(H*num_different-num_inside));
		//h_hi = min(h_hi, (num_inside+sz(remaining))/num_different);
		/*if (target_h > h_hi) {
			cerr << "Using binary search. target_h = " << target_h << " and h_hi = " << h_hi << endl;
			start_binary_search = true;
			target_h = (3*h_lo+h_hi+3)/4;
		}*/
		/*if (!start_binary_search && target_h*num_different < num_inside+num_different/2) {
			target_h++;
		}*/
		/*if (num_queries < 2*N && h_lo >= 1) {
			target_h = max(target_h, int(h_lo+(2*N-num_queries)*(h_lo-0.0)/num_queries));
		}*/
		/*if (!start_binary_search && target_h*num_different < num_inside+h_lo*2) {
			target_h++;
		}*/
		/*if (initial_search) {
			if (h_lo >= target_h) {
				target_h = target_h*2+1;
				if (target_h > h_hi) {
					initial_search = false;
				}
			}
		}
		if (!initial_search) {
			//target_h = (h_lo+h_hi)/2;
			target_h = h_hi;
		}*/
		if (target_h*num_different < num_inside+max(N/100, num_different)) {
			target_h++;
		}
		if (h_lo < 4 && last_added > N/5) {
			target_h = 4;
		}
		target_h = min(target_h, h_hi);
		target_h = max(target_h, h_lo+1);
		//debug();
		if (H > target_h) {
			for (int h = H; h > target_h; --h) {
				while (!at_h[h].empty()) {
					int x = at_h[h].front();
					at_h[h].pop_front();
					_move_outside(x);
					remaining.push_front(x);
				}
			}
			rep(i,0,N)
				min_count_inside[i] = min(min_count_inside[i], target_h);
			H = target_h;
			// assert(H == cur_h());
		}
		if (remaining.empty()) {
			return h_lo;
		}
		int x = remaining.front();
		remaining.pop_front();
		if (min_count_inside[x] >= target_h) {
			remaining.push_back(x);
		} else {
			_move_inside(x);
			if (cur_h() <= target_h) {
				H = cur_h();
				at_h[H].push_back(x);
			} else {
				min_count_inside[x] = H;
				remaining.push_back(x);
				_move_outside(x);
			}
		}
	}
	return h_lo;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:98:7: warning: unused variable 'start_binary_search' [-Wunused-variable]
   98 |  bool start_binary_search = false;
      |       ^~~~~~~~~~~~~~~~~~~
insects.cpp:99:7: warning: unused variable 'initial_search' [-Wunused-variable]
   99 |  bool initial_search = true;
      |       ^~~~~~~~~~~~~~

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