Submission #627644

#	Time	Username	Problem	Language	Result	Execution time	Memory
627644		Tigerpants	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	71 ms	288 KiB

insects

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <random>

using namespace std;

typedef vector<int> vi;
typedef set<int> si;
typedef vector<vi> vvi;
typedef vector<si> vsi;
typedef vector<bool> vb;

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

int min_cardinality(int N) {
    vi x(N);
    for (int i = 0; i < N; i++) {
        x[i] = i;
    }
    
    auto rd = random_device {};
    auto rng = default_random_engine { rd() };
    shuffle(x.begin(), x.end(), rng);

    vb roots(N, false);
    vb inside(N, false);
    vb permanent(N, false);

    int no_roots = 1;
    roots[0] = true;
    move_inside(x[0]);
    inside[0] = true;
    permanent[0] = true;

    for (int i = 1; i < N; i++) {
        move_inside(x[i]);
        inside[i] = true;
        if (press_button() == 2) {
            move_outside(x[i]);
            inside[i] = false;
        } else {
            roots[i] = true;
            permanent[i] = true;
            no_roots++;
        }
    }

    vb active(N, true); // remove those which are too big
    
    if (no_roots == 1) {
        return N;
    }

    if (no_roots == 2) {
        // include root[0]
        // add next
        // press -> get which group
        // remove next
        int a = 1;
        int b = 1;
        for (int i = 1; i < N; i++) {
            if (roots[i]) {
                move_outside(x[i]);
            }
        }
        for (int i = 1; i < N; i++) {
            if (!roots[i]) {
                move_inside(x[i]);
                if (press_button() == 2) {
                    a++;
                } else {
                    b++;
                }
                move_outside(x[i]);
            }
        }
        return min<int>(a, b);
    }

    int no_inside = no_roots;
    
    int high = ((N + no_roots - 1) / no_roots);
    int low = 1;
    while (low + 1 < high) {
        int middle = (low + high) / 2;
        for (int i = 0; i < N; i++) {
            if ((!inside[i]) && (active[i])) {
                move_inside(x[i]);
                inside[i] = true;
                no_inside++;
                if (no_inside >= no_roots + middle) {
                    if (press_button() > middle) {
                        move_outside(x[i]);
                        inside[i] = false;
                        no_inside--;
                    }
                }
            }
        }
        if (no_inside == middle * no_roots) {
            low = middle;
            // don't remove them. make them permanent
            for (int i = 0; i < N; i++) {
                if (inside[i]) {
                    permanent[i] = true;
                }
            }
        } else {
            high = middle;
            // deactivate all higher ones
            // remove all non-permanent ones
            for (int i = 0; i < N; i++) {
                if (!inside[i]) {
                    active[i] = false;
                } else if (!permanent[i]) {
                    move_outside(x[i]);
                    no_inside--;
                    inside[i] = false;
                }
            }
        }
    }

    return low;
}

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