oj.uz

답안 #1059515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1059515 2024-08-15T04:25:10 Z shiomusubi496 드문 곤충 (IOI22_insects) C++17
0 / 100
 40 ms 596 KB 
#include "insects.h"
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

mt19937 mt(random_device{}());

int min_cardinality(int N) {
    int nk = 0;
    vector<bool> f1(N, false), f2(N, false);
    {
        vector<bool> used(N);
        rep (i, N) {
            move_inside(i);
            if (press_button() == 2) move_outside(i);
            else ++nk, used[i] = true;
        }
        f1 = used;
    }
    int ok = 1, ng = N / nk + 1;
    while (ng - ok > 1) {
        int mid = (ok + ng) / 2;
        vector<bool> used(N), used2(N);
        int cnt = 0, lt = -1;
        rep (i, N) {
            if (f1[i]) {
                ++cnt;
                continue;
            }
            if (f2[i]) continue;
            move_inside(i);
            int t = press_button();
            if (t > mid) move_outside(i), used2[i] = true;
            else {
                cnt++, used[i] = true;
                if (lt != mid && t == mid) used2[i] = true;
            }
            lt = t;
        }
        if (cnt == nk * mid) {
            ok = mid;
            rep (i, N) {
                if (used[i]) f1[i] = true;
            }
        }
        else {
            rep (i, N) {
                if (used2[i]) f2[i] = true;
                if (used[i]) move_outside(i);
            }
            ng = mid;
        }
    }
    return ok;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 37 ms 344 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Correct 40 ms 344 KB Output is correct
10 Correct 25 ms 344 KB Output is correct
11 Correct 28 ms 344 KB Output is correct
12 Correct 11 ms 344 KB Output is correct
13 Incorrect 24 ms 344 KB Wrong answer.
14 Halted 0 ms 0 KB -