Submission #731450

#	Time	Username	Problem	Language	Result	Execution time	Memory
731450		alextodoran	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	188 ms	404 KiB

insects

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int E_MAX = 11;

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

int min_cardinality (int N) {
    bool in[N];
    fill(in, in + N, false);
    int dist = 0;
    for (int i = 0; i < N; i++) {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
        } else {
            dist++;
            in[i] = true;
        }
    }
    if (dist == N) {
        return 1;
    }
    int l = 1, r = N / dist;
    while (l < r) {
        int k = (l + r + 1) / 2;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (in[i] == true) {
                move_outside(i);
                in[i] = false;
            }
        }
        for (int i = 0; i < N; i++) {
            move_inside(i);
            if (press_button() > k) {
                move_outside(i);
            } else {
                in[i] = true;
                cnt++;
            }
        }
        if (cnt == dist * k) {
            l = k;
        } else {
            r = k - 1;
        }
    }
    return l;
}

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