Submission #757709

#	Time	Username	Problem	Language	Result	Execution time	Memory
757709		boris_mihov	Rarest Insects (IOI22_insects)	C++17	100 / 100	70 ms	428 KiB

insects

#include "insects.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 2000 + 10;
const int INF  = 1e9;

int n, d;
int perm[MAXN];
bool isInside[MAXN];
std::vector <int> inside;
std::vector <int> toRemove;
std::vector <int> lastlyAdded;

void moveInside(int idx)
{
    assert(!isInside[idx]);
    move_inside(perm[idx]);
}

void moveOutside(int idx)
{
    move_outside(perm[idx]);
}

bool check(int to)
{
    for (int i = 1 ; i <= n ; ++i)
    {
        if (isInside[i])
        {
            continue;
        }

        moveInside(i);
        int res = press_button();
        if (res > to)
        {
            moveOutside(i);
            toRemove.push_back(i);
        } else
        {
            lastlyAdded.push_back(i);
            isInside[i] = true;
        }

        if (lastlyAdded.size() + inside.size() == to * d)
        {
            return true;
        }
    }

    return false;
}

std::mt19937 mt(69);
int min_cardinality(int N) 
{
    n = N;
    std::iota(perm + 1, perm + 1 + n, 0);
    std::shuffle(perm + 1, perm + 1 + n, mt);
    for (int i = 1 ; i <= n ; ++i)
    {
        moveInside(i);
        if (press_button() > 1)
        {
            moveOutside(i);
        } else
        {
            inside.push_back(i);
            isInside[i] = true;
        }
    }

    d = inside.size();
    int l = 1, r = n / d + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        lastlyAdded.clear();
        toRemove.clear();
        if (check(mid))
        {
            l = mid;
            for (const int &i : lastlyAdded)
            {
                inside.push_back(i);
            }
        } else
        {
            r = mid;
            for (const int &i : lastlyAdded)
            {
                moveOutside(i);
                isInside[i] = false;
            }

            for (const int &i : toRemove)
            {
                isInside[i] = true;
            }
        }
    }

    return l;
}

Compilation message (stderr)

insects.cpp: In function 'bool check(int)':
insects.cpp:52:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         if (lastlyAdded.size() + inside.size() == to * d)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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