Submission #736920

#	Time	Username	Problem	Language	Result	Execution time	Memory
736920		onlk97	Rarest Insects (IOI22_insects)	C++17	50 / 100	239 ms	604 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

int min_cardinality(int N) {
    mt19937 mt(time(nullptr));
    vector <int> v;
    for (int i=0; i<N; i++) v.push_back(i);
    shuffle(v.begin(),v.end(),mt);
    set <int> s;
    for (int i=0; i<N; i++){
        move_inside(v[i]);
        s.insert(v[i]);
        int tp=press_button();
        if (tp>1){
            move_outside(v[i]);
            s.erase(v[i]);
        }
    }
    for (int i:s) move_outside(i);
    int cnt=s.size();
    int l=1,r=N/cnt;
    if (cnt==1) return N;
    while (l<r){
        int mid=(l+r+1)/2;
        for (int i=0; i<N; i++){
            move_inside(v[i]);
            s.insert(v[i]);
            int tp=(i+1>=mid?press_button():0);
            if (tp>mid){
                move_outside(v[i]);
                s.erase(v[i]);
            }
        }
        if (s.size()==mid*cnt) l=mid;
        else r=mid-1;
        if (l!=r){
            for (int i:s) move_outside(i);
        }
    }
    return l;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:35:21: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         if (s.size()==mid*cnt) l=mid;
      |             ~~~~~~~~^~~~~~~~~

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