제출 #1229288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229288		LucaIlie	드문 곤충 (IOI22_insects)	C++20	38.65 / 100	60 ms	420 KiB

insects

#include "insects.h"
#include <vector>

using namespace std;

const int MAX_N = 2e3;
int n;
bool getout[MAX_N];
vector<int> distinct, insects;

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

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

        int k = t;
        for (int i: insects) {
            move_inside(i);
            getout[i] = true;
            if (press_button() > mid) 
                move_outside(i);
            else
                k++;
        }

        for (int i: insects) {
            if (getout[i])
                move_outside(i);
            getout[i] = false;
        }

        if (k < mid * t)
            r = mid;
        else
            l = mid;
    }

    return l;
}

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