제출 #1211997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211997		serkanrashid	드문 곤충 (IOI22_insects)	C++20	47.50 / 100	60 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++)
    {
        move_inside(i);
        used[i] = 1;

        int br = press_button();
        if(br > x)
        {
            move_outside(i);
            used[i] = 0;
        }
        else ans++;
    }
    for(int i = 0; i < n; i++) if(used[i]) move_outside(i);
    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)) l = mid+1;
        else r = mid-1;
    }
    return r;
}

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