제출 #1222982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222982		jakobrs	Rarest Insects (IOI22_insects)	C++20	0 / 100	97 ms	408 KiB

insects

#include <numeric>
#include <iostream>
#include <vector>

struct UnionFind {
    std::vector<int> par;

    UnionFind(size_t N) : par(N, -1) {}

    auto find(int idx) -> int {
        if (par[idx] < 0)
            return idx;
        else
            return par[idx] = find(par[idx]);
    }

    void unite(int l, int r) {
        l = find(l);
        r = find(r);

        if (l == r)
            return;
        if (-par[l] < -par[r])
            std::swap(l, r);

        par[l] += par[r];
        par[r] = l;
    }
};

void move_inside(int i);
void move_outside(int i);
int press_button();

int min_cardinality(int N) {
    std::vector<int> included{};

    auto x = [&](int m) -> int {
        for (int i = 0; i < N; i++) {
            move_inside(i);
            if (press_button() > m)
                move_outside(i);
            else
                included.push_back(i);
        }
        auto res = included.size();
        included.clear();
        return res;
    };

    auto k = x(1);

    int l = 1;
    int r = N/k + 1;

    while (r - l > 1) {
        auto m = std::midpoint(l, r);

        auto r = x(m);

        if (r == k * m) {
            l = m;
        } else {
            r = m;
        }
    }

    return l;
}

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