Submission #1281287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281287		Faggi	Rarest Insects (IOI22_insects)	C++20	100 / 100	512 ms	2488 KiB

insects

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();

int N;
vector<bool> cur, target;
map<vector<bool>, int> memo;

inline void mi(int i){ target[i] = true; }
inline void mo(int i){ target[i] = false; }

int pBtn() {
    if (memo.count(target)) return memo[target];
    for (int i = 0; i < N; ++i) {
        if (cur[i] == target[i]) continue;
        if (target[i]) move_inside(i);
        else move_outside(i);
    }
    cur = target;
    return memo[target] = press_button();
}

int min_cardinality(int _N) {
    N = _N;
    cur.assign(N, false);
    target.assign(N, false);

    vector<int> insects(N);
    iota(insects.begin(), insects.end(), 0);

    vector<int> insides, outsides;
    int inside = 0;

    for (int x : insects) {
        mi(x);
        if (pBtn() > 1) {
            mo(x);
            outsides.pb(x);
        } else {
            insides.pb(x);
            ++inside;
        }
    }

    int distinct = inside;
    insects = outsides;

    int l = 1, r = N / distinct, ans = 1;
    while (l <= r) {
        int mid = (l + r + 1) / 2;

        insides.clear();
        outsides.clear();

        for (int x : insects) {
            mi(x);
            if (pBtn() > mid) {
                mo(x);
                outsides.pb(x);
            } else {
                insides.pb(x);
                ++inside;
            }
        }

        if (inside == mid * distinct) {
            ans = mid;
            l = mid + 1;
            insects = outsides;
        } else {
            r = mid - 1;
            insects = insides;
            for (int x : insects) {
                mo(x);
                --inside;
            }
        }
    }

    return ans;
}

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