Submission #1063816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063816		baldwinhuang1	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	169 ms	1400 KiB

insects

#include <bits/stdc++.h>

using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();


bool check(int N, int mid, int uniqueValues) {
    int amountInside = 0;
    // cout << "Mid: " << mid << '\n';
    // cout << press_button() << '\n';
    vector<int> trackInside;
    for (int i = 0; i < N; i++) {
        move_inside(i);
        amountInside++;
        trackInside.push_back(i);
        int curr = press_button();
        if (curr > mid) {
            move_outside(i);
            amountInside--;
            trackInside.erase(trackInside.end() - 1);
        }
        else if (curr == mid && amountInside == (uniqueValues * mid)) {
            for (auto &i: trackInside) {
                move_outside(i);
            }
            return true;
        }
    }
    for (auto &i: trackInside) {
        move_outside(i);
    }
    return false;
}

int min_cardinality(int N) {
    vector<int> mask(N, false);
    int uniqueValues = 0;
    for (int i = 0; i < N; i++) {
        move_inside(i);
        if (press_button() == 1) {
            mask[i] = true;
            uniqueValues++;
            continue;
        }
        else {
            move_outside(i);
        }
    }
    for (int i = 0; i < N; i++) {
        if (mask[i] == true) {
            move_outside(i);
        }
        // cout << mask[i] << ' ';
    }
    
    // cout << check(N, 1024, uniqueValues) << '\n';
    // cout << check(N, 511, uniqueValues) << '\n';
    // cout << check(N, 255, uniqueValues) << '\n';
    // cout << check(N, 127, uniqueValues) << '\n';
    // cout << check(N, 63, uniqueValues) << '\n';
    // cout << check(N, 31, uniqueValues) << '\n';
    // cout << check(N, 15, uniqueValues) << '\n';
    // cout << check(N, 7, uniqueValues) << '\n';
    // cout << check(N, 3, uniqueValues) << '\n';
    // cout << check(N, 1, uniqueValues) << '\n';
    // cout << check(N, 2, uniqueValues) << '\n';
    // return 0;

    int high = 2048; // 2^11
    int low = 0;
    int ans = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        // cout << low << ' ' << high << ' ' << mid << '\n';
        if (check(N, mid, uniqueValues)) {
            // cout << "True" << '\n';
            low = mid + 1;
            ans = mid;
        }
        else {
            // cout << "False" << '\n';
            high = mid - 1;
        }
    }
    return ans;
}

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