Submission #1243739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243739		raphaelp	Rarest Insects (IOI22_insects)	C++20	100 / 100	14 ms	436 KiB

insects

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

int min_cardinality(int N)
{
    vector<int> type(N, 0);
    for (int i = 0; i < N; i++)
        type[i] = i;
    int num = 1;
    swap(type[0], type.back());
    type.pop_back();
    move_inside(0);
    for (int i = 0; i < type.size(); i++)
    {
        move_inside(type[i]);
        int temp = press_button();
        if (temp == 1)
        {
            swap(type[i], type.back());
            type.pop_back();
            i--;
            num++;
        }
        else
            move_outside(type[i]);
    }
    if (num == 1)
        return N;
    int left = N - num, cur = 1;
    while (left)
    {
        int targ = cur + (int)round((double)left / (double)(2 * num));
        int free = targ - cur;
        if (left < num)
            return cur;
        vector<int> news, outs;
        for (int i = 0; i < type.size(); i++)
        {
            move_inside(type[i]);
            int temp = 0;
            if (free == 0)
                temp = press_button();
            else
                free--;
            if (temp > targ)
            {
                outs.push_back(type[i]);
                move_outside(type[i]);
            }
            else
            {
                news.push_back(type[i]);
            }
            if (news.size() == (targ - cur) * num)
            {
                for (int j = i + 1; j < type.size(); j++)
                    outs.push_back(type[j]);
                break;
            }
        }
        if (news.size() == (targ - cur) * num)
        {
            type = outs;
            left -= news.size();
            cur = targ;
        }
        else
        {
            type = news;
            left -= outs.size();
            for (auto v : news)
                move_outside(v);
        }
    }
    return cur;
}

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