제출 #787918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787918		borisAngelov	드문 곤충 (IOI22_insects)	C++17	100 / 100	50 ms	420 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 skip[maxn];
vector<int> to_skip;

int shuffled_indexes[maxn];

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

        move_inside(shuffled_indexes[i]);

        if (press_button() > max_equal)
        {
            to_skip.push_back(i);
            move_outside(shuffled_indexes[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)
    {
        shuffled_indexes[i] = i;
    }

    random_shuffle(shuffled_indexes, shuffled_indexes + n);

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

        int result = press_button();

        if (result > 1)
        {
            move_outside(shuffled_indexes[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();
        to_skip.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(shuffled_indexes[last_add[i]]);
                is_inside[last_add[i]] = false;
            }

            for (int i = 0; i < to_skip.size(); ++i)
            {
                skip[to_skip[i]] = true;
            }
        }
    }

    return l;
}

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

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

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