Submission #1223020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223020		jakobrs	Rarest Insects (IOI22_insects)	C++20	88.32 / 100	26 ms	492 KiB

insects

#include <algorithm>
#include <numeric>
#include <iostream>
#include <set>
#include <vector>

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

int min_cardinality(int N) {
    std::set<int> included{};
    std::vector<int> used{};

    for (int i = 0; i < N; i++)
        used.push_back(i);

    auto eval = [&](int m) -> int {
        for (int x : used) {
            if (included.contains(x))
                continue;
            move_inside(x);
            if (press_button() > m)
                move_outside(x);
            else
                included.insert(x);
        }
        return included.size();
    };

    auto k = eval(1);
    for (auto x : included)
        move_outside(x);
    included.clear();

    int l = 1;
    int r = N/k + 1;
    bool filled = false;

    while (r - l > 1) {
        auto m = (r - l) > 10 ? (l + 2 * (r - l) / 5) : ((l + r) / 2);

        if (filled) {
            used.clear();
            for (auto x : included) {
                used.push_back(x);
                move_outside(x);
            }
            included.clear();
        }

        if (eval(m) == k * m) {
            l = m;
            filled = false;
        } else {
            r = m;
            filled = true;
        }
    }

    return l;
}

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