Submission #1236824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236824		countless	Rarest Insects (IOI22_insects)	C++20	0 / 100	0 ms	408 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);
        }
    }

    int l = 1, r = N / cnt + 1, curr = cnt;
    while (r - l > 1) {
        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);
            }

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

                break;
            }
        }

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

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

            r = m;
        } else {
            for (auto &x : ts) {
                unique.insert(x);
            }

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

            l = m;
        }
    }

    return l;
}

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