Submission #706315

#	Time	Username	Problem	Language	Result	Execution time	Memory
706315		danikoynov	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	324 ms	536 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;

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


    for (int v : vec)
        move_outside(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);
    int lf = 0, rf = 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: 22.5 / 75