Submission #942149

#	Time	Username	Problem	Language	Result	Execution time	Memory
942149		benjaminkleyn	Rarest Insects (IOI22_insects)	C++17	53.16 / 100	95 ms	928 KiB

insects

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

int cnt;
bool inside[2000] = {false};

void init()
{
    cnt = 0;
    memset(inside, false, sizeof(inside));
}
void move_in(int i)
{
    if (inside[i])
        return;
    cnt++;
    inside[i] = true;
    move_inside(i);
}
void move_out(int i)
{
    if (!inside[i])
        return;
    cnt--;
    inside[i] = false;
    move_outside(i);
}

int min_cardinality(int N) 
{
    init();
    for (int i = 0; i < N; i++)
    {
        move_in(i);
        if (press_button() > 1)
            move_out(i);
    }
    int num_types = cnt;

    int lo = 1, hi = N / cnt + 1, mid;
    while (lo < hi)
    {
        mid = lo + (hi - lo + 1) / 2;

        vector<int> new_insects;
        for (int i = N - 1; i >= 0; i--)
            if (!inside[i])
            {
                move_in(i);

                if (press_button() > mid)
                    move_out(i);
                else
                    new_insects.push_back(i);

                if (cnt >= mid * num_types)
                    break;
            }

        if (cnt == mid * num_types)
            lo = mid;
        else
        {
            for (int i : new_insects)
                move_out(i);
            hi = mid - 1;
        }
    }
    return lo;
}

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