Submission #837436

#	Time	Username	Problem	Language	Result	Execution time	Memory
837436		tengiz05	Rarest Insects (IOI22_insects)	C++17	57.29 / 100	140 ms	416 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);
        }
    }
    
    if (cnt <= 7) {
        for (int x : a) move_outside(x);
        int ans = n;
        for (int x : a) {
            move_inside(x);
            int c = 1;
            for (int i = x + 1; i < n; i++) {
                if (binary_search(a.begin(), a.end(), i)) continue;
                move_inside(i);
                if (press_button() > 1) {
                    c++;
                }
                move_outside(i);
            }
            move_outside(x);
            ans = min(ans, c);
        }
        return ans;
    }
    
    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 = 2, hi = n / cnt + 1;
    while (lo < hi) {
        int m = (lo + hi) / 2;
        if (check(m)) {
            lo = m + 1;
        } else {
            hi = m;
        }
    }
    return max(1, lo - 1);
}

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