제출 #766368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766368		adrilen	드문 곤충 (IOI22_insects)	C++17	99.89 / 100	57 ms	412 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;

constexpr int maxn = 2e3 + 9;

bool removed[maxn] = { 0 };

vector <int> in_machine;

int min_cardinality(int n) {
    // Find group

    for (int i = n - 1; i >= 0; i--)
    {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
        } else {
            in_machine.emplace_back(i);
            removed[i] = true;
        }
    }

    int g = in_machine.size();

    int l = 1, r = n / g;
    int mid;
    while (l != r)
    {
        mid = (l + r + 1) >> 1;


        vector <int> taken_out, taken_in;

        for (int i = n - 1; i >= 0; i--)
        {
            if (removed[i]) continue;

            move_inside(i);
            if (press_button() > mid) {
                taken_out.emplace_back(i);
                move_outside(i);
            } else {
                taken_in.emplace_back(i);
                in_machine.emplace_back(i);
            }
        }

        
        if ((int)in_machine.size() == mid * g)
        {
            // Mid is lowerbound
            l = mid;

            for (int i : taken_in) removed[i] = true;
        } else {
            r = mid - 1;

            for (int i : taken_out) removed[i] = true;
            for (int i : taken_in) {
                move_outside(i);
                in_machine.pop_back();
            }
        }
    }


    return l;
}

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