Submission #757689

#	Time	Username	Problem	Language	Result	Execution time	Memory
757689		boris_mihov	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	208 KiB

insects

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

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

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

void moveInside(int 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);
        if (press_button() > to)
        {
            moveOutside(i);
        } else
        {
            lastlyAdded.push_back(i);
            isInside[i] = true;
        }
    }

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

int min_cardinality(int N) 
{
    n = N;
    std::iota(perm + 1, perm + 1 + n, 0);
    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, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        lastlyAdded.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;
            }
        }
    }

    return l;
}

Compilation message (stderr)

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

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