Submission #706340

#	Time	Username	Problem	Language	Result	Execution time	Memory
706340		danikoynov	Rarest Insects (IOI22_insects)	C++17	99.76 / 100	80 ms	328 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>

using namespace std;
const int maxn = 2010;

int par[maxn], rnk[maxn];


int used[maxn], diff, n;

vector < int > safe;
bool check(int x)
{

    int cnt = safe.size();
    vector < int > vec;
    for (int i = 0; i < n && cnt != x * diff; i ++)
    {
        if (!used[i])
            continue;
        move_inside(i);
        vec.push_back(i);
        if (press_button() > x)
        {
            move_outside(i);
            vec.pop_back();
        }
        else
        {
            cnt ++;
        }
    }



        if (cnt != x * diff)
        {
            for (int i = 0; i < n; i ++)
                used[i] = 0;
            for (int v : vec)
                used[v] = 1;
            for (int v : vec)
                    move_outside(v);
        }
        else
        {

            for (int v : vec)
                used[v] = 0, safe.push_back(v);
        }
    return cnt == x * diff;
}

int find_different(int N)
{
        int cnt = 0;
    vector < int > vec;
    for (int i = 0; i < n; i ++)
    {
        move_inside(i);
        vec.push_back(i);
        if (press_button() > 1)
        {
            move_outside(i);
            vec.pop_back();
        }
        else
        {
            cnt ++;
        }
    }

    for (int v : vec)
        move_outside(v);
    return cnt;
}
int min_cardinality(int N)
{
    n = N;
    diff = find_different(N);
    for (int i = 0; i < N; i ++)
        used[i] = 1;
    int lf = 0, rf = N;
    rf = N / diff;
    if (diff == 1)
        return N;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (check(mf))
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    return rf;
}

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