oj.uz

답안 #627498

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

#ifndef RR
#define DEBUG(X)
#endif

/* 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;

    std::set<int> insides;
    int freq = 1;

    auto add = [&] (int i) {
        insides.insert(i);
        move_inside(i);
    };
    auto remove = [&] (int i) {
        insides.erase(i);
        move_outside(i);
    };

    for (int i = 0; i < n; ++i) {
        add(i);
        if (press_button() > 1) {
            remove(i);
        }
    }
    int unique_vals = SZ(insides);
    DEBUG(unique_vals);
    DEBUG(insides);

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

        assert(mid != freq);
        if (mid > freq) {
            for (int i = 0; i < n; ++i) {
                if (!insides.count(i)) {
                    add(i);
                    if (press_button() > mid) {
                        remove(i);
                    }
                }
            }
        } else {
            for (int id : insides) remove(id);
            for (int i = 0; i < n; ++i) {
                add(i);
                if (press_button() > freq) {
                    remove(i);
                }
            }
        }
        freq = mid;
        int total = SZ(insides);

        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 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Runtime error 1 ms 336 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Runtime error 1 ms 336 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Runtime error 1 ms 308 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -