제출 #787904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787904		borisAngelov	드문 곤충 (IOI22_insects)	C++17	0 / 100	53 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;
}

컴파일 시 표준 에러 (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