제출 #1236938

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236938		countless	드문 곤충 (IOI22_insects)	C++20	100 / 100	15 ms	504 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;
    srand(2093475);

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

        unordered_set<int> ts;
        vector<int> o(N);
        iota(o.begin(), o.end(), 0);
        random_shuffle(o.begin(), o.end());
        for (int i = 0; i < N; i++) {
            if (unique.count(o[i])) continue;
            curr++;
            move_inside(o[i]);
            int res = press_button();
            if (res > m) {
                curr--;
                move_outside(o[i]);
                ts.insert(o[i]);
            }

            if (curr == cnt * m) {
                for (int j = i+1; j < N; j++) {
                    if (unique.count(o[j])) continue;
                    ts.insert(o[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: 75 / 75