Submission #800660

#	Time	Username	Problem	Language	Result	Execution time	Memory
800660		QwertyPi	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	54 ms	420 KiB

insects

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

using namespace std;
bool in[2011]; int sz[2011];
int cnt = 0;
void move_in(int i){
    assert(!in[i]);
    in[i] = true;
    move_inside(i);
    cnt++;
}

void move_out(int i){
    assert(in[i]);
    in[i] = false;
    move_outside(i);
    cnt--;
}

int min_cardinality(int N) {
    fill(in, in + N, 0);
    fill(sz, sz + N, 0);
    for(int i = 0; i < N; i++){
        move_in(i);
        int c = press_button();
        if(c >= 2) sz[i] = 2, move_out(i);
    }
    int K = cnt;

    int L = 1, R = N / K;
    while(L != R){
        int M = (L + R + 1) / 2;
        vector<int> added;
        int prv = -1;
        for(int i = 0; i < N; i++){
            if(in[i] || sz[i] > M) continue;
            move_in(i); added.push_back(i);
            int c = press_button();
            if(prv != -1 && c > prv) sz[i] = c;
            if(c > M) move_out(i), added.pop_back();
            prv = min(c, M);
        }
        if(cnt == M * K){
            L = M;
        }else{
            for(auto i : added){
                move_out(i);
            }
            R = M - 1;
        }
    }
    return L;
}

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