Submission #1229325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229325		LucaIlie	드문 곤충 (IOI22_insects)	C++20	0 / 100	14 ms	436 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e3;
int n;
bool getout[MAX_N];
vector<int> distinct, insects;
mt19937 rnd(100111);

int min_cardinality(int N) {
    n = N;

    move_inside(0);
    distinct.push_back(0);
    for (int i = 1; i < n; i++) {
        move_inside(i);
        if (press_button() == 2) {
            move_outside(i);
            insects.push_back(i);
        }
        else
            distinct.push_back(i);
    }
    int t = distinct.size();

    if (t == 1)
        return n;

    if (t == 2) {
        int f = 1;
        for (int i = 1; i < n; i++) {
            move_inside(i);
            int t = press_button();
            if (t != f + 1)
                move_outside(i);
            else
                f++;
        }
        return min(f, n - f);
    }

    int l = 1, r = n / t;
    int ans = 1;
    int k = t;
    while (r - l > 0) {
        int mid = (l + r) / 2;

        k = l * t;
        int maxP = 0;
        shuffle(insects.begin(), insects.end(), rnd);
        vector<int> remInsects, elimInsects;
        for (int i: insects) {
            move_inside(i);
            getout[i] = true;
            int p = press_button();
            if (p > mid) {
                move_outside(i);
                elimInsects.push_back(i);
            }
            else {
                k++;
                maxP = max(maxP, p);
                remInsects.push_back(i);
            }
        }

        if (k < mid * t) {
            r = maxP - 1;
            for (int i: insects) {
                if (getout[i]) {
                    move_outside(i);
                    getout[i] = false;
                    k--;
                }
            }
            insects = remInsects;
        } else {
            l = mid + 1;
            ans = mid;
            insects = elimInsects;
        }
    }

    return ans;
}

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