Submission #721474

#	Time	Username	Problem	Language	Result	Execution time	Memory
721474		buidangnguyen05	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	208 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;

        // cerr << mid << "\n";

        int cnt = 0;
        for (int i : items) {
            if (!inside[i]) {
                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 {
            n = cnt;
            set<int> nxt;
            for (int i : items) if (inside[i]) {
                inside[i] = 0;
                move_outside(i);
                nxt.insert(i);
            }
            items = nxt;

            R = mid - 1;
        }
    }

    return res;
}

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