Submission #627500

#	Time	Username	Problem	Language	Result	Execution time	Memory
627500		I_love_Hoang_Yen	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	200 ms	544 KiB

insects

#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 {
            auto ids = insides;
            for (int id : ids) remove(id);

            for (int i = 0; i < n; ++i) {
                add(i);
                if (press_button() > mid) {
                    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: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 22.5 / 75