Submission #1145680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145680		Pannda	Rarest Insects (IOI22_insects)	C++20	48.13 / 100	57 ms	436 KiB

insects

#include "insects.h"

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

int min_cardinality(int n) {
    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;
        for (int i : outside) {
            if (n - outside.size() + moved_inside.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;
    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: 23.13 / 75