Submission #672101

#	Time	Username	Problem	Language	Result	Execution time	Memory
672101		tbzard	Rarest Insects (IOI22_insects)	C++17	10 / 100	224 ms	372 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;
        int search = mid;

        vector<int> add;
        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 == search) idx = mid, hi = mid-1;
                    else lo = mid+1;
                    for(int i=0;i<=mid;i++){
                        move_inside(v[i]);
                    }
                }
                move_outside(i);
                check[idx] = 1;
            }
            else add.push_back(i);
        }
        for(int i=0;i<(int)add.size();i++){
            move_outside(add[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: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75