Submission #1235565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235565		Ghulam_Junaid	Rarest Insects (IOI22_insects)	C++20	99.89 / 100	15 ms	428 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
// #include "stub.cpp"
using namespace std;

const int MXN = 2005;
int sz;
bool a[MXN], dead[MXN], alive[MXN];

bool add(int i){
    if (a[i] or dead[i]) return 0;
    sz++;
    a[i] = 1;
    move_inside(i);
    return 1;
}

bool rem(int i){
    if (!a[i] or alive[i]) return 0;
    sz--;
    a[i] = 0;
    move_outside(i);
    return 1;
}

int get(){
    return press_button();
}

int min_cardinality(int n){
    int d = 0;    
    for (int i = 0; i < n; i ++){
        add(i);
        if (get() == 2)
            rem(i);
        d += a[i];
        if (a[i]) alive[i] = 1;
    }
    if (d == 1) return n;

    int l = 1, r = n / d + 1;
    vector<int> kil, pro;
    while (r - l > 1){
        int mid = (l + r) / 2;

        for (int i = 0; i < n; i ++)
            rem(i);

        int last = l;
        for (int i = 0; i < n; i ++){
            if (!add(i)) continue;
            int val = get();
            if (val > mid or (last < mid and val == mid))
                kil.push_back(i);
            if (val <= mid)
                pro.push_back(i);
            if (val > mid)
                rem(i);
            else last = val;
        }

        if (sz == d * mid){
            kil.clear();
            for (int i : pro)
                alive[i] = 1;
            pro.clear();
            l = mid;
        }
        else{
            pro.clear();
            for (int i : kil)
                dead[i] = 1;
            kil.clear();
            r = mid;
        }

    }

    return l;
}

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