Submission #727777

#	Time	Username	Problem	Language	Result	Execution time	Memory
727777		vjudge1	Rarest Insects (IOI22_insects)	C++17	0 / 100	0 ms	208 KiB

insects

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

int min_cardinality(int N) {
    std::vector<int>machine;
    std::vector<bool>inside(N,false),fixed(N,false);
    for(int i=0;i<N;++i){
        move_inside(i);
        if(press_button()==2){
            move_outside(i);
        }
        else{
            inside[i]=fixed[i]=true;
            machine.eb(i);
        }
    }
    int uni=machine.size();
    int l=1,r=N/uni;
    while(l<r){
        int mid=(l+r+1)>>1,k=0;
        for(int i=0;i<N;++i){
            if(fixed[i]) continue;
            if(uni*mid==k) break;
            move_inside(i);
            k++;
            if(press_button()>mid){
                move_outside(i);
                k--;
            }
            else{
                inside[i]=true;
                machine.eb(i);
            }
        }
        if(uni*mid==k){
            l=mid;
            for(int i=0;i<N;++i){
                if(inside[i]) fixed[i]=true;
            }
        }
        else{
            r=mid-1;
            for(int i=0;i<N;++i){
                if(!inside[i]){
                    fixed[i]=true;
                }
                else if(!fixed[i]){
                    move_outside(i);
                    inside[i]=false;
                    machine.pop_back();
                }
            }
        }
    }
    return l;
}

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