Submission #800676

#	Time	Username	Problem	Language	Result	Execution time	Memory
800676		QwertyPi	Rarest Insects (IOI22_insects)	C++17	100 / 100	59 ms	448 KiB

insects

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

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

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

int min_cardinality(int N) {
    mt19937 rng(0);
    for(int i = 0; i < N; i++) p[i] = i;
    for(int i = 0; i < N; i++) swap(p[i], p[rng() % (i + 1)]);
    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;
    fill(mx, mx + N, N + 1);
    while(L != R){
        int M = (L + R) / 2 + 1;
        for(int i = 0; i < N; i++){
            if(mx[i] != N + 1 && mx[i] > M){
                mx[i] = N + 1; move_out(i);
            }
        }
        int prv = -1;
        for(int i = 0; i < N; i++){
            if(in[p[i]] || sz[i] > M) continue;
            move_in(i);
            int c = press_button(); mx[i] = c;
            if(prv != -1 && c > prv) sz[i] = c;
            if(c > M) move_out(i), mx[i] = N + 1;
            prv = min(c, M);
        }
        if(cnt == M * K){
            L = M;
        }else{
            R = cnt / K;
        }
    }
    return L;
}

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