← Real problems

ioi22p5

unratedStatement on DMOJ

CP Lang

35 lineschecks
// IOI 2022 "Rarest Insects": interactive; a machine reports the largest
// group of one type among the insects inside it. Find the rarest type's size.
// Greedily filling the machine with at most `cap` of each type takes exactly
// kinds * cap insects iff every type has at least cap, which is monotone in cap.
extern fn move_inside(i: Int)
extern fn move_outside(i: Int)
extern fn press_button() -> Int

@grader
fn min_cardinality(n: Int) -> Int:
    domain Insect = [n]
    var inside: [Insect]Bool = false

    fn fill(cap: Int) -> List<Insect>:
        var added = List<Insect>()
        for i in Insect if not inside[i]:
            move_inside(Int(i))
            if press_button() > cap:
                move_outside(Int(i))
            else:
                inside[i] = true
                added.push(i)
        added

    let kinds = fill(1).len
    fn holds(cap: Int) -> Bool:
        let added = fill(cap)
        if inside.count(x => x) == kinds * cap:
            return true
        for i in added:
            move_outside(Int(i))
            inside[i] = false
        false

    (1..=n / kinds).last_true(holds)!

Accepted C++

90 lines · 6.56 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(size(x))

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

int min_cardinality(int n) {
    set<int> s;
    auto move_in = [&](int i) -> void {
        move_inside(i);
        assert(!s.count(i));
        s.insert(i);
    };
    auto move_out = [&](int i) -> void {
        move_outside(i);
        assert(s.count(i));
        s.erase(i);
    };
    auto press_but = [&]() -> int {
        assert(sz(s));
        return press_button();
    };
    for (int i = 0; i < n; i++) {
        move_in(i);
        if (press_but() > 1) {
            move_out(i);
        }
    }
    int distinct_cnt = sz(s);
    int l = 1, r = n / distinct_cnt;
    while (l < r) {
        int mid = max(l + 1, (4 * l + 1 * r) / 5);
        vector<int> outside, changed;
        for (int i = 0; i < n; i++) {
            if (!s.count(i)) {
                outside.push_back(i);
            }
        }
        for (int i = 0; i < sz(outside); i++) {
            if (sz(s) + sz(outside) - i < distinct_cnt * mid) {
                break;
            }
            int x = outside[i];
            move_in(x);
            if (press_but() > mid) {
                move_out(x);
            } else {
                changed.push_back(x);
            }
        }
        if (sz(s) == distinct_cnt * mid) {
            l = mid;
        } else {
            r = mid - 1;
            for (auto& a : changed) {
                move_out(a);
            }
        }
    }
    return l;
}