Submission #628862

#	Time	Username	Problem	Language	Result	Execution time	Memory
628862		phathnv	Rarest Insects (IOI22_insects)	C++17	100 / 100	96 ms	428 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000;

bool isIn[MAX_N], nxt[MAX_N];

int ask(const vector<int> &a) {
    for (int i = 0; i < MAX_N; ++i) {
        nxt[i] = 0;
    }
    for (auto x : a) {
        nxt[x] = 1;
    }
    for (int i = 0; i < MAX_N; ++i) {
        if (isIn[i] > nxt[i]) {
            move_outside(i);
        }
        if (isIn[i] < nxt[i]) {
            move_inside(i);
        }
        isIn[i] = nxt[i];
    }
    return press_button();
}

int min_cardinality(int n) {
    vector<int> a(n);
    iota(a.begin(), a.end(), 0);
    srand(123);
    random_shuffle(a.begin(), a.end());

    vector<int> nxt, inside;
    for (auto x : a) {
        inside.push_back(x);
        if (ask(inside) > 1) {
            inside.pop_back();
            nxt.push_back(x);
        }
    }
    int numDistinct = inside.size();
    int res = 1;
    a = nxt;

    int l = 1, r = (int) a.size() / numDistinct;
    while (l <= r) {
        int mid = (l + r) >> 1;

        vector<int> outside;
        inside.clear();
        for (auto x : a) {
            if ((int)inside.size() == mid * numDistinct) {
                outside.push_back(x);
                continue;
            }

            inside.push_back(x);
            if ((int)inside.size() <= mid) {
                continue;
            }
            if (ask(inside) > mid) {
                inside.pop_back();
                outside.push_back(x);
            }
        }
        if ((int)inside.size() == numDistinct * mid) {
            res += mid;
            a = outside;
            l = 1;
            r = (int)a.size() / numDistinct;
        } else {
            a = inside;
            l = max(1, (int)a.size() - mid * (numDistinct - 1));
            r = (int)a.size() / numDistinct;
        }
    }

    return res;
}

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