제출 #1235547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235547		Ghulam_Junaid	드문 곤충 (IOI22_insects)	C++20	99.89 / 100	15 ms	436 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
// #include "stub.cpp"
using namespace std;

const int MXN = 2005;
int sz;
bool a[MXN], dead[MXN], alive[MXN];

bool add(int i){
    if (a[i] or dead[i]) return 0;
    sz++;
    a[i] = 1;
    move_inside(i);
    return 1;
}

bool rem(int i){
    if (!a[i] or alive[i]) return 0;
    sz--;
    a[i] = 0;
    move_outside(i);
    return 1;
}

int get(){
    return press_button();
}

int min_cardinality(int n){
    int d = 0;    
    for (int i = 0; i < n; i ++){
        add(i);
        if (get() == 2)
            rem(i);
        d += a[i];
        if (a[i]) alive[i] = 1;
    }
    if (d == 1) return n;

    int last = 1;
    int l = 1, r = n / d + 1;
    vector<int> kil, pro;
    while (r - l > 1){
        int mid = (l + r) / 2;

        if (mid < last){
            for (int i = 0; i < n; i ++)
                rem(i);
        }

        for (int i = 0; i < n; i ++){
            if (!add(i)) continue;
            if (get() > mid){
                rem(i);
                kil.push_back(i);
            }
            else
                pro.push_back(i);
        }

        if (sz == d * mid){
            kil.clear();
            for (int i : pro)
                alive[i] = 1;
            pro.clear();
            l = mid;
        }
        else{
            pro.clear();
            for (int i : kil)
                dead[i] = 1;
            kil.clear();
            r = mid;
        }

        last = mid;
    }

    return l;
}

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