Submission #1185398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185398		anmattroi	드문 곤충 (IOI22_insects)	C++17	25 / 100	90 ms	424 KiB

insects

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

using namespace std;

int ok(int N, int X) {
    for (int i = 0; i < N; i++) move_outside(i);
    vector<int> A, B;
    for (int i = 0; i < N; i++) {
        move_inside(i);
        int T = press_button();
        if (T > X) {
            move_outside(i);
            A.emplace_back(i);
        }
    }
    for (int i = 0; i < N; i++) move_outside(i);
    for (int i = 0; i < N; i++) {
        move_inside(i);
        int T = press_button();
        if (T >= X) {
            move_outside(i);
            B.emplace_back(i);
        }
    }
    int diff = int(B.size()) - int(A.size());
    return diff * X < N - int(A.size());
}
int min_cardinality(int N) {

    int lo = 1, hi = N+1;
    while (hi - lo > 1) {
        int mid = (lo + hi) >> 1;
        if (ok(N, mid)) hi = mid;
        else lo = mid;
    }
    return lo;
}

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