Submission #672106

#	Time	Username	Problem	Language	Result	Execution time	Memory
672106		tbzard	Rarest Insects (IOI22_insects)	C++17	47.51 / 100	205 ms	456 KiB

insects

#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();

bool vis[2222];
int min_cardinality(int n){
    vector<int> v;
    for(int i=0;i<n;i++){
        move_inside(i);
        int r = press_button();
        if(r == 2) move_outside(i);
        else{
            v.push_back(i);
            vis[i] = 1;
        }
    }

    int ans = n/(int)v.size();
    int lo = 1, hi = ans-1;
    while(lo <= hi){
        int mid = (lo+hi)/2;

        vector<int> add;
        int cnt = 0;
        for(int i=0;i<n;i++){
            if(vis[i]) continue;

            move_inside(i);
            int r = press_button();
            if(r == mid+2){
                move_outside(i);
            }
            else{
                add.push_back(i);
                cnt++;
            }
        }
        for(int i=0;i<(int)add.size();i++){
            move_outside(add[i]);
        }
        if(cnt < (int)v.size()*mid) ans = mid, hi = mid-1;
        else lo = mid+1;
    }

    return ans;
}

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