oj.uz

Submission #837249

# Submission time Handle Problem Language Result Execution time Memory
837249 2023-08-25T08:37:22 Z tengiz05 Rarest Insects (IOI22_insects) C++17
0 / 100
 1 ms 208 KB 
#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.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 75.0

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