Submission #1145690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145690		Pannda	Rarest Insects (IOI22_insects)	C++20	100 / 100	14 ms	432 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();
    int siz = 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 (siz == d * b) {
                new_outside.push_back(i);
                continue;
            }
            move_inside(i); siz++;
            if (press_button() > b) {
                move_outside(i); siz--;
                new_outside.push_back(i);
            } else {
                moved_inside.push_back(i);
            }
        }
        if (siz == d * b) {
            outside = new_outside;
            return true;
        } else {
            for (int i : moved_inside) {
                move_outside(i); siz--;
            }
            outside = moved_inside;
            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: 75 / 75