제출 #1355916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355916		po_rag526	Rarest Insects (IOI22_insects)	C++20	10 / 100	72 ms	420 KiB

insects

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void dbg() { cout << "\n"; }
template<typename H, typename... T>
void dbg(H h, T... t) {
    cout << h << " ";
    dbg(t...);
}

#include "insects.h"
const int N = 2020;
int mark[N];

int min_cardinality(int n) {
    vector<int> v;
    int k = 0;
    for (int i = 0; i < n; i++) {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
        } else {
            mark[i] = 1;
            v.push_back(i);
            k++;
        }
    }
    int ans = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < n; j++) {
            if (mark[j]) continue;
            move_inside(j);
            if (press_button() > i) {
                move_outside(j);
            } else {
                mark[j] = 1;
                v.push_back(i);
            }
        }
        // dbg(i,v.size());
        if (v.size() == k*i) ans = i;
        else break;
    }
    // int l = 1, r = n/k, ans = 0;
    // while (l <= r) {
    //     int mid = (l+r)/2;
    //     int cnt = 0;
    //     for (auto x : v) move_outside(x);
    //     v.clear();
    //     for (int i = 0; i < n; i++) {
    //         move_inside(i);
    //         if (press_button() > mid) {
    //             move_outside(i);
    //         } else {
    //             v.push_back(i);
    //             cnt++;
    //         }
    //     }
    //     if (cnt == k*mid) l = mid+1, ans = mid;
    //     else r = mid-1;
    // }
    return ans;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 0 / 15
• 서브태스크 3: 0 / 75