Submission #1243721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243721		raphaelp	Rarest Insects (IOI22_insects)	C++20	0 / 100	2079 ms	408 KiB

insects

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

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

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