제출 #837374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837374		tengiz05	Rarest Insects (IOI22_insects)	C++17	50.01 / 100	151 ms	460 KiB

insects

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

int min_cardinality(int n) {
    int cnt = n;
    move_inside(0);
    vector<int> a{0};
    for (int i = 1; i < n; i++) {
        move_inside(i);
        if (press_button() == 2) {
            cnt--;
            move_outside(i);
        } else {
            a.push_back(i);
        }
    }
    auto check = [&](int m) {
        vector<int> b;
        int bad = 0;
        for (int i = 0; i < n; i++) {
            if (!binary_search(a.begin(), a.end(), i)) {
                move_inside(i);
                if (press_button() <= m) {
                    b.push_back(i);
                } else {
                    move_outside(i);
                    bad++;
                }
            }
        }
        for (int x : b) {
            move_outside(x);
        }
        if (n - bad == m * cnt) {
            return true;
        } else {
            return false;
        }
    };
    int lo = 2, hi = n / cnt + 1;
    while (lo < hi) {
        int m = (lo + hi) / 2;
        if (check(m)) {
            lo = m + 1;
        } else {
            hi = m;
        }
    }
    return max(1, lo - 1);
}

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