제출 #677356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677356		Ninja_Kunai	드문 곤충 (IOI22_insects)	C++17	100 / 100	56 ms	416 KiB

insects

/**
*    Author :  Nguyen Tuan Vu
*    Created : 03.01.2023
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + rng() % (r - l + 1);}

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

void move_inside(int i);
void move_outside(int i);
int press_button();

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