Submission #727783

#	Time	Username	Problem	Language	Result	Execution time	Memory
727783		vjudge1	Rarest Insects (IOI22_insects)	C++17	100 / 100	59 ms	428 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);
        }
    }
    std::vector<int>id;
    for(int i=0;i<N;i+=2){
        id.eb(i);
    }
    for(int i=1;i<N;i+=2){
        id.eb(i);
    }
    int uni=machine.size();
    int l=1,r=N/uni;
    while(l<r){
        int mid=(l+r+1)>>1;
        for(auto to:id){
            int i=to;
            if(fixed[i]) continue;
            if(uni*mid==machine.size()) break;
            move_inside(i);
            if(press_button()>mid){
                move_outside(i);
            }
            else{
                inside[i]=true;
                machine.eb(i);
            }
        }
        if(uni*mid==machine.size()){
            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;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             if(uni*mid==machine.size()) break;
      |                ~~~~~~~^~~~~~~~~~~~~~~~
insects.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if(uni*mid==machine.size()){
      |            ~~~~~~~^~~~~~~~~~~~~~~~

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