oj.uz

Submission #1063788

# Submission time Handle Problem Language Result Execution time Memory
1063788 2024-08-18T02:35:04 Z baldwinhuang1 Rarest Insects (IOI22_insects) C++17
0 / 100
 0 ms 344 KB 
#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 = N / 2;
    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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Wrong answer.
3 Halted 0 ms 0 KB -