Submission #1063787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063787		baldwinhuang1	Rarest Insects (IOI22_insects)	C++17	25 / 100	209 ms	916 KiB

insects

#include <bits/stdc++.h>

using namespace std;

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

vector<int> memo(2000, -1);

bool check(int N, int mid, int uniqueValues) {
    if (memo[mid] != -1) {
        return memo[mid];
    }
    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--;
        }
        else if (curr == mid && amountInside == (uniqueValues * mid)) {
            for (auto &i: trackInside) {
                move_outside(i);
            }
            memo[mid] = true;
            return true;
        }
    }
    for (auto &i: trackInside) {
        move_outside(i);
    }
    memo[mid] = false;
    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, 1000, uniqueValues) << '\n';
    // cout << check(N, 500, uniqueValues) << '\n';

    int high = 2000;
    int low = 0;
    while (low <= high) {
        int mid = (high + low) / 2;
        // cout << low << ' ' << high << ' ' << mid << ' ' <<  check(N, mid, uniqueValues) << '\n';
        if (low == high) {
            return mid;
        }
        else {
            if (check(N, mid, uniqueValues) && !check(N, mid + 1, uniqueValues)) {
                return mid;

            }
            else if (check(N, mid, uniqueValues)) {
                low = mid + 1;
            }
            else {
                high = mid;
            }
        }
    }
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:44:30: warning: control reaches end of non-void function [-Wreturn-type]
   44 |     vector<int> mask(N, false);
      |                              ^

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