제출 #721473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721473		buidangnguyen05	드문 곤충 (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