oj.uz

답안 #627483

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
627483 2022-08-12T15:33:39 Z I_love_Hoang_Yen 드문 곤충 (IOI22_insects) C++17
0 / 100
 1 ms 208 KB 
#include "insects.h"
#include "bits/stdc++.h"
#define SZ(s) ((int) s.size())
using namespace std;

/* sub1
// Sub 1 {{{
int min_cardinality(int n) {
    std::vector<int> v_ids(n);
    std::iota(v_ids.begin(), v_ids.end(), 0);

    std::set<int> ids(v_ids.begin(), v_ids.end());
    int freq = 0, last_cnt = 0;

    while (true) {
        ++freq;
        std::set<int> new_ids;

        for (int id : ids) {
            move_inside(id);
            if (press_button() > freq) {
                move_outside(id);
                new_ids.insert(id);
            }
        }

        int unique_values = SZ(ids) - SZ(new_ids);
        if (unique_values < last_cnt) {
            return freq - 1;
        }
        last_cnt = unique_values;

        if (unique_values > SZ(new_ids)) {
            return freq;
        }

        ids = std::move(new_ids);
    }

    return 0;
}
// }}}
*/

int get_max_freq(int n) {
    for (int i = 0; i < n; ++i) {
        move_inside(i);
    }
    int res = press_button();
    for (int i = 0; i < n; ++i) {
        move_outside(i);
    }
    return res;
}

int cnt_unique(int n) {
    int res = n;
    std::set<int> ids;
    for (int i = 0; i < n; ++i) {
        move_inside(i);
        ids.insert(i);
        if (press_button() == 2) {
            --res;
            move_outside(i);
            ids.erase(i);
        }
    }

    for (int id : ids) move_outside(id);
    return res;
}

int min_cardinality(int n) {
    int l = 2, r = get_max_freq(n), res = 1;
    int unique_vals = cnt_unique(n);

    while (l <= r) {
        int mid = (l + r) / 2;

        std::set<int> ids;
        for (int i = 0; i < n; ++i) {
            move_inside(i);
            ids.insert(i);
            if (press_button() > mid) {
                move_outside(i);
                ids.erase(i);
            }
        }

        int total = SZ(ids);
        for (int id : ids) move_outside(id);

        std::cout << mid << " -> " << total << std::endl;

        if (total >= unique_vals * mid) {
            // all values have at least frequency = mid
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return res;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Secret mismatch (possible tampering with the output)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Secret mismatch (possible tampering with the output)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB Secret mismatch (possible tampering with the output)
2 Halted 0 ms 0 KB -