Submission #1236837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236837		countless	Rarest Insects (IOI22_insects)	C++20	99.88 / 100	15 ms	452 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;

    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);
        }
    }

    int l = 0, r = N / cnt, curr = cnt, ans = 1;
    while (l <= r) {
        int m = (l + r) / 2;

        unordered_set<int> ts;
        for (int i = 0; i < N; i++) {
            if (unique.count(i)) continue;
            curr++;
            move_inside(i);
            int res = press_button();
            if (res > m) {
                curr--;
                move_outside(i);
                ts.insert(i);
            }

            if (curr == cnt * m) {
                for (int j = i+1; j < N; j++) {
                    if (unique.count(j)) continue;
                    ts.insert(j);
                }

                break;
            }
        }

        if (curr == cnt * m) {
            for (int i = 0; i < N; i++) {
                unique.insert(i);
            }

            for (auto &x : ts) {
                unique.extract(x);
            }

            ans = m;
            l = m + 1;
        } else {
            for (auto &x : ts) {
                unique.insert(x);
            }

            for (int i = 0; i < N; i++) {
                if (unique.count(i)) continue;
                move_outside(i);
                curr--;
            }

            r = m - 1;
        }
    }

    return ans;
}

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