제출 #787911

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

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;
}

mt19937 mt(69420);

int min_cardinality(int N)
{
    n = N;

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

    shuffle(new_array, new_array + n, mt);

    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();

        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(new_array[last_add[i]]);
                is_inside[last_add[i]] = false;
            }
        }
    }*/

    for (int i = 1; i <= 10; ++i)
    {
        if (check(i) == true)
        {
            return i;
        }
    }

    return -1;
}

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