Submission #676641

#	Time	Username	Problem	Language	Result	Execution time	Memory
676641		MilosMilutinovic	Rarest Insects (IOI22_insects)	C++17	100 / 100	59 ms	416 KiB

insects

#include "insects.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int N = 2023;
int n;
int d;
int c;
bool used[N];
bool skip[N];

void findDistinct() {
	vector<int> p;
	for (int i = 0; i < n; i++) {
		move_inside(i);
		if (press_button() == 1)
			p.push_back(i);
		else
			move_outside(i);
	}
	for (int i : p) used[i] = true;
	d = (int) p.size();
}

bool check(int x) {
	c = 0;
	for (int i = 0; i < n; i++)
		c += used[i];
	vector<int> ids;
	for (int i = 0; i < n; i++)
		if (!used[i] && !skip[i])
			ids.push_back(i);
	shuffle(all(ids), rng);
	vector<int> p, q;
	for (int i : ids) {
		move_inside(i);
		if (press_button() > x)
			move_outside(i), q.push_back(i);
		else
			c++, p.push_back(i);
		if (c == x * d)
			break;
	}
	if (c == x * d) {
		for (int i : p) used[i] = true;
		return true;
	} else {
		for (int i : p) move_outside(i);
		for (int i : q) skip[i] = true;
		return false;
	}
}

int min_cardinality(int N) {
	n = N;
	findDistinct();
	if (d == 1)
		return N;
//	if (d == 2) {
//		for (int i = 0; i < N; i++)
//			if (!used[i])
//				move_inside(i);
//		return n - press_button();
//	}
	int l = 1, r = n / d + 1;
	while(r - l > 1) {
		int mid = (l + r) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid, r = min(r, c / d + 1);
	}
	return l;
}

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