제출 #1145682

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

insects

#include "insects.h"

#include <bits/stdc++.h>
using namespace std;

int min_cardinality(int n) {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> outside;
    for (int i = 0; i < n; i++) {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
            outside.push_back(i);
        }
    }
    int d = n - outside.size();
    auto check = [&](int b) -> bool {
        vector<int> moved_inside;
        vector<int> new_outside;
        shuffle(outside.begin(), outside.end(), rng);
        for (int i : outside) {
            if (n - outside.size() + moved_inside.size() == d * b || n - outside.size() + moved_inside.size() + ( outside.size() - moved_inside.size() - new_outside.size() ) < d * b) {
                new_outside.push_back(i);
                continue;
            }
            move_inside(i);
            if (press_button() > b) {
                move_outside(i);
                new_outside.push_back(i);
            } else {
                moved_inside.push_back(i);
            }
        }
        if (n - new_outside.size() == d * b) {
            outside = new_outside;
            return true;
        } else {
            for (int i : moved_inside) {
                move_outside(i);
            }
            return false;
        }
    };
    int l = 1;
    int r = n / d;
    while (l < r) {
        int m = (l + r + 1) >> 1;
        if (check(m)) {
            l = m;
        } else {
            r = m - 1;
        }
    }
    return l;
}

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