Submission #672095

#	Time	Username	Problem	Language	Result	Execution time	Memory
672095		tbzard	Rarest Insects (IOI22_insects)	C++17	0 / 100	3096 ms	208 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];
bool check[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){
        memset(check, 0, sizeof(check));
        int mid = (lo+hi)/2;
        for(int i=0;i<n;i++){
            if(vis[i]) continue;

            move_inside(i);
            int r = press_button();
            if(r > mid){
                int lo = 0, hi = (int)v.size()-1, idx;
                while(lo <= hi){
                    int mid = (lo+hi)/2;
                    for(int i=0;i<mid;i++){
                        move_outside(v[i]);
                        int r = press_button();
                        if(r == mid) idx = mid, hi = mid-1;
                        else lo = mid+1;
                        move_inside(v[i]);
                    }
                }
                check[idx] = 1;
            }
            move_outside(i);
        }
        bool ok = 0;
        for(int i=0;i<(int)v.size();i++){
            if(!check[i]){
                ok = 1;
                break;
            }
        }
        if(ok) ans = mid, hi = mid-1;
        else lo = mid+1;
    }

    return ans;
}

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