Submission #1222930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222930		jakobrs	Rarest Insects (IOI22_insects)	C++20	0 / 100	0 ms	396 KiB

insects

#include <numeric>
#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) {
    move_inside(0);

    auto dsu = UnionFind(N);

    auto included = std::vector<int>{0};

    for (int i = 1; i < N; i++) {
        move_inside(i);

        int card = press_button();

        if (card > 1) {
            int l = 0;
            int r = included.size();
            bool filled = true;

            while (r - l > 1) {
                // We know that the index of the equal one satisfies l <= idx < r
                auto m = std::midpoint(l, r);

                // We want to test if l <= idx < m
                if (filled) {
                    for (int j = m; j < r; j++)
                        move_outside(included[j]);
                } else {
                    for (int j = l; j < m; j++)
                        move_inside(included[j]);
                }

                if (press_button() > 1) {
                    r = m;
                    filled = true;
                } else {
                    l = m;
                    filled = false;
                }
            }

            dsu.unite(i, included[l]);

            if (filled)
                move_inside(included[l]);
            for (int j = r; j < included.size(); j++)
                move_inside(included[j]);
        } else {
            included.push_back(i);
        }
    }

    int best = -dsu.par[dsu.find(0)];
    for (int i = 0; i < N; i++) {
        if (dsu.par[i] > 0)
            continue;

        best = std::min(best, -dsu.par[i]);
    }

    return best;
}

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