Submission #736769

#	Time	Username	Problem	Language	Result	Execution time	Memory
736769		jk410	Rarest Insects (IOI22_insects)	C++17	99.56 / 100	78 ms	308 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int n;
bool used[2000],check[2000][2];
int mySolve[2001];
int solve(int x) {
	int& ret = mySolve[x];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = 0; i < n; i++) {
		if (!check[i][0] && !check[i][1]) {
			move_inside(i);
			used[i] = true;
			if (press_button() > x) {
				used[i] = false;
				move_outside(i);
			}
		}
		if (used[i])
			ret++;
	}
	return ret;
}
int min_cardinality(int _n) {
	n = _n;
	memset(mySolve, -1, sizeof(mySolve));
	int cnt = solve(1);
	int l = 1, r = n / cnt, ans;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (solve(m) == cnt * m) {
			for (int i = 0; i < n; i++) {
				if (used[i])
					check[i][0] = true;
			}
			ans = m;
			l = m + 1;
		}
		else {
			for (int i = 0; i < n; i++) {
				if (!used[i])
					check[i][1] = true;
				if (used[i] && !check[i][0]) {
					used[i] = false;
					move_outside(i);
				}
			}
			r = m - 1;
		}
	}
	return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:53:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |  return ans;
      |         ^~~

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