제출 #1261170

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

insects

#include <bits/stdc++.h>
using namespace std;
vector<int> inside;
unordered_set<int> sett;
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N)
{
    // number of different types
    for (int i = 0; i < N; i++)
    {
        move_inside(i);
        if (press_button() > 1)
        {
            move_outside(i);
            sett.insert(i);
        }
        else
            inside.push_back(i);
    }
    int l = 1;
    int r = N / inside.size();
    // binary search
    while (l < r)
    {
        int m = l + (r - l + 1) / 2;
        vector<int> w;
        vector<int> outs;
        for (int i : sett)
        {
            move_inside(i);
            if (press_button() > m)
            {
                move_outside(i);
                outs.push_back(i);
            }
            else
                w.push_back(i);
        }
        if (w.size() == inside.size() * (m - l))
        {
            l = m;
            for (int i : w)
                sett.erase(i);
        }
        else
        {
            for (int i : outs)
                sett.erase(i);
            for (int i : w)
                move_outside(i);
            r = m - 1;
        }
    }
    return l;
}

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