Submission #797546

#	Time	Username	Problem	Language	Result	Execution time	Memory
797546		TahirAliyev	Rarest Insects (IOI22_insects)	C++17	100 / 100	47 ms	324 KiB

insects

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

using namespace std;
//press_button
//move_outside
//move_inside

bool Inside[2001];

int min_cardinality(int N) {
    move_inside(0);
    Inside[0] = 1;

    int k = 1;
    for (int i = 1; i < N; i++)
    {
        move_inside(i);
        if(press_button() == 2){
            move_outside(i);
        }
        else{
            Inside[i] = 1;
            k++;
        }
    }
    vector<int> v;
    for (int i = 0; i < N; i++)
    {
        v.push_back(i);
    }
    random_shuffle(v.begin(), v.end());
    int l = 2, r = N / k;
    int ans = 1;
    int t = k;
    while(l <= r){
        int mid = (l + r) / 2;
        vector<int> added;
        vector<int> bl;
        for (int i : v)
        {
            if(t == mid * k) break;
            if(Inside[i]){
                continue;
            }
            move_inside(i);
            if(press_button() == mid + 1){
                move_outside(i);
                bl.push_back(i);
            }
            else{
                Inside[i] = 1;
                t++;
                added.push_back(i);
            }
        }
        if(t == mid * k){
            l = mid + 1;
            ans = mid;
        }
        else{
            r = mid - 1;
            for(int i : added){
                move_outside(i);
                Inside[i] = 0;
                t--;
            }
            for(int i : bl){
                Inside[i] = 1;
            }
        }
    }
    return ans;
}

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