Submission #837249

#	Time	Username	Problem	Language	Result	Execution time	Memory
837249		tengiz05	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	208 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

int min_cardinality(int n) {
    int cnt = n;
    move_inside(0);
    vector<int> a{0};
    for (int i = 1; i < n; i++) {
        move_inside(i);
        if (press_button() == 2) {
            cnt--;
            move_outside(i);
        } else {
            a.push_back(i);
        }
    }
    auto check = [&](int m) {
        vector<int> b;
        int bad = 0;
        for (int i = 0; i < n; i++) {
            if (!binary_search(a.begin(), a.end(), i)) {
                move_inside(i);
                if (press_button() <= m) {
                    b.push_back(i);
                } else {
                    move_outside(i);
                    bad++;
                }
            }
        }
        for (int x : b) {
            move_outside(x);
        }
        if (n - bad == m * cnt) {
            return true;
        } else {
            return false;
        }
    };
    int lo = 1, hi = n / cnt;
    while (lo < hi) {
        int m = (lo + hi) / 2;
        if (check(m)) {
            hi = m;
        } else {
            lo = m + 1;
        }
    }
    return lo;
}

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