Submission #1214211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214211		thangdz2k7	Rarest Insects (IOI22_insects)	C++20	99.89 / 100	15 ms	428 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

int min_cardinality(int N){
    vector <int> used(N, 0);
    int num = 0;

    auto add = [&](int i) -> void {
        if (used[i]) return;
        move_inside(i);
        num ++;
        used[i] = 1;
    };

    auto del = [&](int i) -> void {
        if (!used[i]) return;
        move_outside(i);
        num --;
        used[i] = 0;
    };

    auto qry = [&]() -> int {
        if (num == 1) return 1;
        return press_button();
    };

    for (int i = 0; i < N; ++ i){
        add(i);
        if (qry() > 1) del(i);
    }

    if (num == 1) return N;
    if (num == N) return 1;

    int D = num;
    vector <int> valid = used;
    vector <int> ban(N, 0);

    auto check = [&](int mid){
        vector <int> g;
        for (int i = 0; i < N; ++ i){
            if (!used[i] && !ban[i]){
                add(i);
                if (qry() > mid) {
                    del(i);
                    g.push_back(i);
                }
            }
        }

        if (num == D * mid){
            valid = used;
            return true;
        }

        for (int i = 0; i < N; ++ i) if (!valid[i]) del(i);
        for (int i : g) ban[i] = 1;

        return false;
    };

    int low = 1, high = N / D;
    while (low < high){
        int mid = (low + high + 1) >> 1;
        if (check(mid)) low = mid;
        else high = mid - 1;
    }

    return low;
}

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