Submission #787903

#	Time	Username	Problem	Language	Result	Execution time	Memory
787903		borisAngelov	Rarest Insects (IOI22_insects)	C++17	0 / 100	55 ms	312 KiB

insects

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

using namespace std;

const int maxn = 2005;

int n;

vector<int> machine;
bool is_inside[maxn];

int machine_initial_size = 0;

vector<int> last_add;

int new_array[maxn];

bool check(int max_equal)
{
    for (int i = 0; i <= n - 1; ++i)
    {
        if (is_inside[i] == true)
        {
            continue;
        }

        move_inside(new_array[i]);

        if (press_button() > max_equal)
        {
            move_outside(new_array[i]);
        }
        else
        {
            last_add.push_back(i);
            is_inside[i] = true;
        }

        int curr_size = last_add.size() + machine.size();

        if (curr_size == max_equal * machine_initial_size)
        {
            return true;
        }
    }

    return false;
}

int min_cardinality(int N)
{
    n = N;

    for (int i = 0; i <= n - 1; ++i)
    {
        new_array[i] = i;
    }

    random_shuffle(new_array, new_array + n);

    for (int i = 0; i <= n - 1; ++i)
    {
        move_inside(new_array[i]);

        int result = press_button();

        if (result > 1)
        {
            move_outside(new_array[i]);
        }
        else
        {
            machine.push_back(i);
            is_inside[i] = true;
            ++machine_initial_size;
        }
    }

    if (machine_initial_size == 1)
    {
        return n;
    }

    int l = 1;
    int r = n / machine_initial_size + 1;

    vector<int> answers(n + 5, -1);

    while (l < r - 1)
    {
        int mid = (l + r) / 2;

        last_add.clear();

        int result = answers[mid];

        if (result == -1)
        {
            result = check(mid);
            answers[mid] = result;
        }

        if (result == true)
        {
            l = mid;

            for (int i = 0; i < last_add.size(); ++i)
            {
                machine.push_back(last_add[i]);
            }
        }
        else
        {
            r = mid;

            for (int i = 0; i < last_add.size(); ++i)
            {
                move_outside(last_add[i]);
                is_inside[last_add[i]] = false;
            }
        }
    }

    return l;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:108:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for (int i = 0; i < last_add.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~
insects.cpp:117:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             for (int i = 0; i < last_add.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~

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