제출 #1236818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236818		countless	드문 곤충 (IOI22_insects)	C++20	47.52 / 100	59 ms	456 KiB

insects

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

int min_cardinality(int N) {
    int cnt = 0, add = 0;

    unordered_set<int> unique;
    for (int i = 0; i < N; i++) {
        cnt++;
        move_inside(i);
        unique.insert(i);
        int res = press_button();
        if (res == 2) {
            cnt--;
            move_outside(i);
            unique.extract(i);
        }
    }
    
    auto check = [&](int m) -> bool {
        unordered_set<int> ts;
        int curr = cnt + add;
        for (int i = 0; i < N; i++) {
            if (unique.count(i)) continue;
            curr++;
            move_inside(i);
            ts.insert(i);
            int res = press_button();
            if (res > m) {
                curr--;
                move_outside(i);
                ts.extract(i);
            }
        }

        if (curr >= cnt * m) {
            for (auto &x : ts) unique.insert(x);
            add += ts.size();
        } else {
            for (auto &x : ts) move_outside(x);
        }

        return curr < cnt * m;
    };

    int l = 0, r = N / cnt;
    while (r - l > 1) {
        int m = (l + r) / 2;

        if (check(m)) {
            r = m;
        } else {
            l = m;
        }
    }

    if (check(r)) r = l;

    return r;
}

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