Submission #977605

#	Time	Username	Problem	Language	Result	Execution time	Memory
977605		Vedang1006	Rarest Insects (IOI22_insects)	C++17	47.52 / 100	128 ms	1088 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"

using namespace std;

bool used[2000];
bool used2[2000];

void tryFillUsed2(int N, int target)
{
    for (int i = 0; i < N; i++)
    {
        if (!used[i])
        {
            move_inside(i);
            if (press_button() > target) move_outside(i);
            else
            {
                used2[i] = true;
            }
        }
    }
}

int min_cardinality(int N)
{
    int numberOfDistinctTypes = 0;

    for (int i = 0; i < N; i++)
    {
        move_inside(i);
        if (press_button() != 1) move_outside(i);
        else
        {
            numberOfDistinctTypes += 1;
            used[i] = true;
        }
    }

    int i = 1;

    for (int j = 1024; j > 0; j /= 2)
    {
        if (i + j <= 2000)
        {
            tryFillUsed2(N, i + j);
            int totalSumUsed2 = 0;
            for (int i = 0; i < N; i++) totalSumUsed2 += used[i] + used2[i];

            if (numberOfDistinctTypes * (i + j) != totalSumUsed2)
            {
                for (int idx = 0; idx < N; idx++)
                {
                    if (used2[idx]) move_outside(idx);
                    used2[idx] = false;
                }
            }
            else
            {
                for (int idx = 0; idx < N; idx++)
                {
                    used[idx] |= used2[idx];
                    used2[idx] = false;
                }

                i += j;
            }
        }
    }

    return i;
}

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