Submission #627606

#	Time	Username	Problem	Language	Result	Execution time	Memory
627606		Tigerpants	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	65 ms	292 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) {
    vb roots(N, false);
    vb inside(N, false);
    vb permanent(N, false);

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

    for (int i = 1; i < N; i++) {
        move_inside(i);
        inside[i] = true;
        if (press_button() == 2) {
            move_outside(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;
    }

    int no_inside = no_roots;
    
    int high = (N / no_roots) + 1;
    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(i);
                inside[i] = true;
                no_inside++;
                if (press_button() > middle) {
                    move_outside(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(i);
                    no_inside--;
                    inside[i] = false;
                }
            }
        }
    }

    return low;
}

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