Submission #628766

#	Time	Username	Problem	Language	Result	Execution time	Memory
628766		tranxuanbach	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	99 ms	1204 KiB

insects

#include "insects.h"
#include "bits/stdc++.h"
 
#define SZ(s) ((int) s.size())
using namespace std;
 
#ifndef RR
#define DEBUG(X)
#endif

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::high_resolution_clock::now().time_since_epoch().count());
using randint_t = uniform_int_distribution<int>;
using randll_t = uniform_int_distribution<long long>;
using randd_t = uniform_real_distribution<double>;
// return x with probability p, y with probability 1-p
template<class T>
T pick(T x, T y, double p = 0.5){
    assert(-0.0001 <= p && p <= 1.0001);
    return randd_t(0, 1)(rng) <= p ? x : y;
}
int randr(int l, int r){
    return randint_t(l, r)(rng);
}
 
/*
int min_cardinality(int n) {
    int res = n + 1;  // final result
 
    // used(i) = true if we already counted species of i
    std::vector<bool> used(n, false);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            // set containing all insects of this species
            std::set<int> same_species {i};
            move_inside(i);
 
            for (int j = i + 1; j < n; ++j) {
                if (!used[j]) {
                    move_inside(j);
                    if (press_button() == 1 + SZ(same_species)) {
                        same_species.insert(j);
                    } else {
                        move_outside(j);
                    }
                }
            }
 
            res = std::min(res, SZ(same_species));
 
            // remove all insects from machine
            for (int j : same_species) {
                move_outside(j);
                used[j] = true;
            }
        }
    }
    return res;
}
*/
 
int min_cardinality(int n) {
    std::vector<int> perm(n); iota(perm.begin(), perm.end(), 0); shuffle(perm.begin(), perm.end(), rng);
    std::set<int> insides;  // set of insects inside machine
    // lambda functions {{{
    // lambda function to add one insect to machine
    auto add = [&] (int i) { move_inside(perm[i]); insides.insert(i); };
    // lambda function to remove one insect from machine
    auto remove = [&] (int i) { move_outside(perm[i]); insides.erase(i); };
    // }}}
 
    // machine_states(f) = set of insects inside machine after we
    //                     binary search with value f
    std::map<int, std::set<int>> machine_states;
 
    // Step 1: Find set containing unique insects
    for (int i = 0; i < n; ++i) {
        add(i);
        if (press_button() > 1) {  // this species appeared before
            remove(i);
        }
    }
    int unique_vals = SZ(insides);
 
    machine_states[1] = insides;
    machine_states[n] = std::set<int>();
    for (int i = 0; i < n; ++i) machine_states[n].insert(i);
 
    // Step 2: Binary search for min f
    int l = 2, r = n / unique_vals, res = 1;
    while (l <= r) {
        int mid = (l + r) / 2;
 
        assert(mid > res);
        auto it = machine_states.lower_bound(mid);
        std::set<int> just_added;
        for (int i : it->second) if (!insides.count(i)) {
            add(i);
            if (press_button() > mid) remove(i);
            else just_added.insert(i);
        }
        int total = SZ(insides);
        machine_states[mid] = insides;
 
        if (total >= unique_vals * mid) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
            if (mid - (unique_vals * mid - total) >= l){
                res = mid - (unique_vals * mid - total);
                l = mid - (unique_vals * mid - total) + 1;
            }
            for (int i : just_added) {
                remove(i);
            }
        }
    }
    return res;
}
 
/* 53.16
int min_cardinality(int n) {
    std::set<int> insides;  // set of insects inside machine
    // lambda functions {{{
    // lambda function to add one insect to machine
    auto add = [&] (int i) { move_inside(i); insides.insert(i); };
    // lambda function to remove one insect from machine
    auto remove = [&] (int i) { move_outside(i); insides.erase(i); };
    // }}}
 
    std::set<int> last_machine_state;  // store previous `good` state
 
    // Step 1: Find set containing unique insects
    for (int i = 0; i < n; ++i) {
        add(i);
        if (press_button() > 1) {  // this species appeared before
            remove(i);
        }
    }
    int unique_vals = SZ(insides);
 
    // Step 2: Binary search for min f
    int l = 2, r = n / unique_vals, res = 1;
    while (l <= r) {
        int mid = (l + r) / 2;
 
        assert(mid > res);
        std::set<int> just_added;
        for (int i = 0; i < n; ++i) if (!insides.count(i)) {
            add(i);
            if (press_button() > mid) remove(i);
            else just_added.insert(i);
        }
        int total = SZ(insides);
 
        if (total >= unique_vals * mid) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
            for (int i : just_added) {
                remove(i);
            }
        }
    }
    return res;
}
*/

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 74.89 / 75