Submission #721473

#	Time	Username	Problem	Language	Result	Execution time	Memory
721473		buidangnguyen05	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	179 ms	596 KiB

insects

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

using namespace std;

const int N = 2e3 + 10;
bool inside[N];
set<int> items;
int n;

int min_cardinality(int _n) {
    n = _n;

    for (int i = 0; i < n; ++i) items.insert(i);

    int types = 0;
    for (int i = 0; i < n; ++i) {
        inside[i] = 1;
        move_inside(i);
        ++types;
        if (press_button() == 2) {
            inside[i] = 0;
            move_outside(i);
            --types;
        }
    }

    int L = 1, R = n / types, res = 1;
    while (L <= R) {
        int mid = (L + R) >> 1;

        for (int i : items) if (inside[i]) {
            inside[i] = 0;
            move_outside(i);
        }

        int cnt = 0;
        for (int i : items) {
            inside[i] = 1;
            move_inside(i);
            ++cnt;

            if (press_button() > mid) {
                inside[i] = 0;
                move_outside(i);
                --cnt;
            }
        }

        if (cnt == types * mid) {
            res = mid;
            L = mid + 1;
        }
        else R = mid - 1;
    }

    return res;
}

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