Submission #721496

#	Time	Username	Problem	Language	Result	Execution time	Memory
721496		buidangnguyen05	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	206 ms	528 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;
        }
    }

    for (int i = 0; i < n; ++i) if (inside[i]) {
        inside[i] = 0;
        move_outside(i);
    }

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

        set<int> turn;

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

                turn.insert(i);
            }
            cnt += inside[i];

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

                turn.erase(i);
            }
        }

        if (cnt == types * mid) {
            res = mid;
            L = mid + 1;
        }
        else {
            set<int> nxt;
            for (int i : items) if (inside[i]) nxt.insert(i);
            for (int i : turn) {
                inside[i] = 0;
                move_outside(i);
            }
            items = nxt;

            R = mid - 1;
        }
    }

    return res;
}

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