Submission #1212000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212000		serkanrashid	Rarest Insects (IOI22_insects)	C++20	49.01 / 100	57 ms	424 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

const int MAXN = 2048;
int n,p;
int used[MAXN];

bool check(int x)
{
    int ans = 0;
    for(int i = 0; i < n; i++) if(used[i] == 1) move_outside(i);

    for(int i = 0; i < n; i++)
    {
        if(used[i] == 10) ans++;

        if(used[i] == 10) continue;
        if(used[i] == -1) continue;

        move_inside(i);
        used[i] = 1;

        int br = press_button();
        if(br > x)
        {
            move_outside(i);
            used[i] = 0;
        }
        else ans++;
    }
    return ans == x*p;
}

int min_cardinality(int N)
{
    n = N;
    int gr = n;


    /*for(int i = 0; i < n; i++)
    {
        move_inside(i);
    }
    gr = press_button();


    for(int i = 0; i < n; i++) move_outside(i);*/

    p = 0;
    for(int i = 0; i < n; i++)
    {
        move_inside(i);
        used[i] = 1;
        int br = press_button();
        if(br > 1)
        {
            move_outside(i);
            used[i] = 0;
        }
        else p++;
    }


    int l = 1, r = gr;
    int mid;
    while(l <= r)
    {
        mid = (l+r)/2;
        if(check(mid))
        {
            for(int i = 0; i < n; i++) if(used[i] == 1) used[i] = 10;
            l = mid+1;
        }
        else
        {
            for(int i = 0; i < n; i++) if(used[i] == 0) used[i] = -1;
            r = mid-1;
        }
    }
    return r;
}

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