Submission #1186006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186006		anmattroi	Rarest Insects (IOI22_insects)	C++17	99.83 / 100	15 ms	444 KiB

insects

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

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> p;

int cnt;

int pressButton() {
    return press_button();
}

void moveInside(int i) {
    move_inside(p[i]);
}

void moveOutside(int i) {
    move_outside(p[i]);
}

int minCardinality(int N) {
    vector<int> candidates(N);
    iota(candidates.begin(), candidates.end(), 0);

    int coef = 0;

    int lo = 1, hi = N/cnt+1;
    while (hi - lo > 1) {
        hi = min(hi, coef + int(candidates.size() / cnt) + 1);
        int mid = (lo + hi) >> 1;
//        cout << lo << ' ' << mid << ' ' << hi << ' ' << candidates.size() << "\n";
        vector<int> inside, outside;
        int fl = 0;
        for (int i : candidates) {
            if (coef * cnt + int(inside.size()) == mid*cnt || fl) {
                fl = 1;
                outside.emplace_back(i);
                continue;
            }
            moveInside(i);
            if (pressButton() > mid) {
                moveOutside(i);
                outside.emplace_back(i);
            } else inside.emplace_back(i);
        }

        if (coef * cnt + int(inside.size()) == mid * cnt) {
            lo = mid;
            coef = mid;
            candidates = outside;
        } else {
            for (int i : inside) moveOutside(i);
            hi = mid;
            candidates = inside;
        }
    }
    return lo;
}
/*
9
4 4 4 4 3 3 3 3 3 3
*/
/*
4
2 2 2 3
*/

int min_cardinality(int N) {
    p.assign(N, 0);
    iota(p.begin(), p.end(), 0);
//    shuffle(p.begin(), p.end(), rng);

    vector<int> e;
    for (int i = 0; i < N; i++) {
        moveInside(i);
        if (pressButton() > 1) moveOutside(i);
        else {
            e.emplace_back(i);
            ++cnt;
        }
    }
    for (int i : e) moveOutside(i);
    if (cnt == 1) return N;
    if (cnt == 2) {
        for (int i = 0; i < N; i++) moveInside(i);
        int T = pressButton();
        int O = N-T;
        if (O == 0) O = INT_MAX;
        return min(O, T);
    }
    if (cnt == N-1) return 1;
    if (cnt == N) return 1;


    return minCardinality(N);
}
/*
2000
30 12 14 20 12 19 43 20 5 9 18 18 33 24 11 41 10 28 33 2 5 5 41 25 23 0 33 18 39 2 19 24 12 14 12 13 13 40 8 6 13 41 18 20 19 31 23 25 30 20 36 11 32 17 5 9 14 27 16 38 6 15 2 8 11 36 23 9 20 30 34 23 40 13 31 34 16 30 13 5 3 43 10 21 5 20 10 14 16 6 16 11 30 35 18 40 19 8 3 25 23 10 35 27 0 25 37 4 1 31 21 19 26 8 17 2 2 19 18 33 20 28 39 3 5 18 9 2 12 26 11 21 1 3 21 27 28 41 16 10 18 27 8 8 15 18 40 10 15 19 34 22 37 39 2 5 20 39 24 6 12 22 11 27 26 25 28 12 3 17 31 33 31 4 28 14 14 24 29 10 18 19 13 23 43 41 30 19 22 14 9 25 27 25 4 27 42 14 31 25 33 4 33 11 39 38 37 16 2 0 24 31 15 35 8 16 17 30 10 18 0 17 12 9 31 12 40 22 9 11 28 8 38 3 0 21 12 3 29 19 4 9 20 7 26 3 7 1 8 42 30 40 8 9 33 29 28 13 39 1 7 0 38 36 30 35 24 27 36 36 0 25 38 20 16 25 8 15 2 17 38 0 17 13 34 19 41 20 42 1 15 42 31 26 26 25 14 13 13 20 13 21 9 20 10 4 39 11 16 15 1 15 24 27 37 2 23 0 28 7 9 25 21 13 26 23 17 4 14 1 15 12 34 12 13 36 38 20 0 13 0 10 38 11 9 4 10 2 3 25 3 14 1 16 25 18 34 1 35 16 1 17 7 4 40 34 3 22 37 13 31 5 2 9 4 11 32 28 12 24 1 12 28 31 36 9 26 36 0 3 7 3 7 10 28 19 15 3 17 35 16 8 43 35 4 36 42 4 22 21 24 3 43 10 30 5 0 28 11 17 2 9 43 21 36 9 24 8 4 23 36 1 29 17 18 6 8 35 12 26 8 32 31 8 7 20 31 3 10 14 11 3 13 32 30 21 0 0 2 12 17 7 33 35 20 1 4 31 33 4 15 25 28 4 24 13 22 3 10 36 21 4 15 6 0 10 3 4 9 2 19 15 30 31 7 27 0 29 30 26 26 0 14 1 40 11 17 5 37 9 18 8 43 37 15 0 10 25 12 22 8 9 5 0 25 24 10 3 11 13 0 6 10 8 21 7 40 12 1 16 14 5 41 0 36 3 28 25 38 34 23 23 9 17 5 41 32 35 35 17 29 29 9 20 24 21 1 30 3 29 20 19 27 26 19 22 8 2 17 23 0 31 5 9 22 29 13 17 43 36 41 32 5 7 0 33 5 3 21 19 0 12 1 29 15 18 13 14 19 1 25 3 9 30 16 29 8 23 0 16 17 15 20 20 28 32 2 2 31 33 6 16 42 25 6 26 37 6 40 8 41 36 14 7 22 19 27 30 41 16 4 3 19 9 14 9 22 3 19 21 24 9 32 22 37 0 12 23 26 38 30 6 1 43 18 20 35 28 5 7 20 34 10 3 37 36 19 39 29 23 21 28 18 17 6 6 20 37 29 0 16 3 8 3 1 0 0 15 19 41 21 10 29 4 23 5 33 2 24 3 18 9 26 33 11 12 42 30 6 26 24 2 41 8 26 37 22 29 26 13 42 16 3 0 11 10 11 34 32 27 18 11 25 14 7 15 2 36 39 13 10 36 17 1 27 22 26 10 3 17 32 4 6 21 3 23 28 18 21 1 4 38 41 27 30 3 8 31 15 17 21 11 42 30 27 23 5 24 42 16 1 6 35 3 38 28 19 0 0 6 13 32 5 24 39 8 3 28 1 2 12 27 9 26 9 21 8 2 0 31 14 7 31 21 6 7 3 28 2 23 17 24 1 19 20 5 17 5 22 5 12 13 28 7 2 25 9 18 4 10 32 12 30 9 3 29 42 6 4 5 33 32 5 9 18 25 38 26 25 30 16 8 31 16 6 14 8 6 4 15 24 12 9 15 32 12 19 17 26 29 32 21 34 23 13 3 9 0 5 19 35 5 10 6 0 38 29 7 4 40 3 9 2 4 25 1 25 20 35 17 2 37 33 1 24 28 5 27 22 3 34 3 9 1 15 22 1 34 40 25 39 6 4 3 37 14 26 4 5 11 11 43 0 35 8 20 13 42 4 14 39 33 28 3 21 28 14 0 12 17 29 37 37 14 11 25 5 7 10 6 21 36 4 1 15 1 22 39 20 18 2 4 7 33 29 28 35 32 3 32 17 4 28 23 16 6 12 37 24 17 25 27 27 12 12 8 25 2 25 36 22 15 24 5 6 34 23 10 3 16 14 8 9 14 38 7 20 21 8 39 29 20 17 1 5 29 4 6 41 4 42 26 34 28 8 24 30 25 10 24 9 34 22 33 8 32 18 13 3 20 32 14 4 43 38 16 36 40 27 18 8 21 8 42 7 12 42 15 18 31 19 0 11 43 7 8 12 4 13 22 7 24 32 7 6 15 9 4 12 23 10 5 22 3 12 27 34 16 4 42 7 5 22 23 18 12 43 28 4 27 1 24 37 3 19 24 24 22 17 29 5 10 7 16 28 20 36 29 32 10 33 2 39 24 29 18 18 19 40 39 11 28 11 34 34 19 6 32 9 34 6 41 1 23 41 5 2 7 26 5 40 11 23 2 16 1 0 25 7 29 35 21 30 21 5 18 30 31 17 0 6 20 7 34 13 41 10 42 4 43 15 18 7 9 6 13 22 29 33 2 20 24 35 4 7 5 4 28 2 20 4 37 5 31 26 35 1 16 26 36 19 9 1 12 2 9 16 9 27 18 1 10 1 7 38 38 21 5 32 7 23 20 5 26 7 26 34 43 8 25 39 12 7 38 35 43 23 39 27 13 37 17 37 21 10 4 2 19 17 11 26 25 12 13 7 8 29 11 12 10 2 24 23 9 21 19 6 19 0 13 3 21 12 6 11 1 38 6 23 16 2 4 19 38 1 22 19 1 14 0 7 0 43 37 38 2 14 33 13 27 19 13 27 19 8 11 0 8 2 21 27 10 26 2 1 6 20 4 14 4 39 14 11 28 28 29 1 23 17 25 10 29 30 12 11 26 13 8 5 3 10 36 8 27 32 32 2 42 9 11 0 18 0 32 39 5 14 27 5 20 2 40 32 7 20 5 11 23 1 1 8 17 4 2 36 32 15 5 43 16 9 11 9 25 1 0 36 20 2 15 14 21 27 0 17 7 12 1 29 37 0 21 12 23 13 33 41 23 6 39 40 15 19 21 7 30 42 14 33 30 38 0 22 4 1 22 2 11 9 18 36 40 22 39 13 40 27 34 22 15 30 30 22 15 22 7 0 16 40 7 7 10 38 1 4 33 6 10 2 3 35 34 5 16 1 29 6 2 4 32 8 27 25 17 1 8 0 7 11 40 27 35 14 14 11 14 31 17 10 33 32 0 31 10 5 13 19 26 14 19 30 6 3 33 2 23 20 36 6 16 30 16 4 13 14 11 23 34 0 2 18 16 2 3 3 14 21 9 8 4 6 16 13 17 5 14 3 19 8 39 38 26 37 3 7 11 15 11 10 35 19 11 31 12 28 2 5 9 11 24 22 31 32 5 2 41 0 36 23 12 40 1 18 37 12 34 20 30 14 18 0 26 28 18 11 19 24 27 2 40 13 5 15 15 4 1 20 6 0 31 39 24 23 30 12 3 13 43 9 11 37 11 2 33 31 10 26 23 16 14 2 34 35 11 13 40 7 10 0 38 17 10 6 28 4 1 35 7 17 43 6 15 18 7 1 43 21 43 5 10 31 34 19 17 22 22 21 25 1 8 25 6 8 6 42 17 27 12 21 16 43 13 18 2 23 29 17 22 0 26 7 12 0 29 6 20 7 19 22 15 16 7 33 19 1 7 17 16 29 25 2 22 0 14 26 6 0 38 24 31 10 35 14 21 6 22 3 12 24 2 8 4 9 3 28 16 15 20 30 22 29 8 3 8 4 28 11 34 15 16 0 18 9 15 6 11 9 35 16 27 14 3 18 1 16 29 41 7 21 15 13 5 13 11 35 10 6 2 24 13 15 12 4 39 7 34 5 19 4 16 7 15 39 18 1 17 14 13 39 16 15 3 14 6 15 0 37 31 6 41 13 32 1 2 11 11 24 10 10 20 7 6 34 4 14 31 38 10 11 0 21 6 5 35 41 7 2 4 15 16 26 20 40 15 14 14 13 3 24 22 1 32 6 1 27 9 1 15 8 36 37 33 37 35 32 10 24 40 23 41 41 4 31 24 30 38 21 9 11 8 42 23 10 20 33 42 22 27 13 12 11 36 37 10 32 33 26 18 22 14 33 18 15 25 6 35 34 17 7 13 0 41 12 5 18 2 6 1 42 12 5 2 8 12 2 15 8 40 24 13 23 18 15 9 34 17 22 26 10 21 39 5 30 6 15 42 29 27 18 5 18 8 1 6 14 33 23 31 16 16
*/

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