Submission #1185407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185407		anmattroi	Rarest Insects (IOI22_insects)	C++17	25 / 100	71 ms	436 KiB

insects

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

using namespace std;


int ok(int N, int X) {
    vector<int> A, B;

    for (int i = 0; i < N; i++) {
        move_inside(i);
        int T = press_button();
        if (T >= X) {
            move_outside(i);
            B.emplace_back(i);
        }
    }
    for (int i : B) {
        move_inside(i);
        int T = press_button();
        if (T > X) {
            move_outside(i);
            A.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;
        if (lo != hi) for (int i = 0; i < N; i++) move_outside(i);
    }
    return lo;
}

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