Submission #672120

#	Time	Username	Problem	Language	Result	Execution time	Memory
672120		tbzard	Rarest Insects (IOI22_insects)	C++17	91.81 / 100	71 ms	424 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;
    vector<int> add;
    int cnt = 0;
    int k = 1;
    while(lo <= hi){
        int mid = (lo+hi)/2;

        if(mid >= k){
            for(int i=0;i<n;i++){
                if(vis[i]) continue;

                move_inside(i);
                int r = press_button();
                k = r;
                if(r == mid+2){
                    move_outside(i);
                    k = r-1;
                }
                else{
                    vis[i] = 1;
                    add.push_back(i);
                    cnt++;
                }
            }
        }
        else{
            vector<int> out;
            while(!add.empty()){
                int i = add.back();

                move_outside(i);
                vis[i] = 0;
                add.pop_back();
                cnt--;
                out.push_back(i);
                int r = press_button();
                k = r;
                if(r < mid+2){
                    break;
                }
            }
            for(int j=0;j<(int)out.size();j++){
                int i = out[j];
                if(vis[i]) continue;

                move_inside(i);
                int r = press_button();
                k = r;
                if(r == mid+2){
                    move_outside(i);
                    k = r-1;
                }
                else{
                    vis[i] = 1;
                    add.push_back(i);
                    cnt++;
                }

            }
        }

        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: 66.81 / 75