제출 #787889

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

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

        move_inside(i);

        if (press_button() > max_equal)
        {
            move_outside(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)
    {
        move_inside(i);

        int result = press_button();

        if (result > 1)
        {
            move_outside(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;

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

        last_add.clear();

        if (check(mid) == 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 r;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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