제출 #1232606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232606		nicolo_010	드문 곤충 (IOI22_insects)	C++20	10 / 100	98 ms	436 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)

int min_cardinality(int N) {
	random_device rd;
	mt19937 gen(rd());
	v<int> pool(N);
	rep(i, 0, N) pool[i] = i;
	int ans = 1e9;
	rep(i, 0, min(40, N)) {
		if (pool.size() == 0) break;
		//cout << i << " " << pool.size() << " ";
		//for (auto x : pool) cout << x << " ";
		//cout << endl;
		int r = pool.size();
		uniform_int_distribution<> dis(0, r-1);
		int idx = dis(gen);
		v<int> to_erase;
		idx = pool[idx];
		to_erase.push_back(idx);
		//cout << "IN: " << idx << " ";
		move_inside(idx);
		int cmp = 1;
		for (auto x : pool) {
			if (x == idx) continue;
			move_inside(x);
			int a = press_button();
			if (a == 2) {
				to_erase.push_back(x);
				cmp++;
				//cout << x << " ";
			}
			move_outside(x);
		}
		//cout << endl;
		move_outside(idx);
		ans = min(cmp, ans);
		//cout << to_erase.size() << endl;
		for (auto x : to_erase) {
			//cout << "TOERASE: " << x << endl;
			auto it = find(pool.begin(), pool.end(), x);
			pool.erase(it);
		}
		//to_erase.clear();
	}
	return ans;
}

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