Submission #736906

#	Time	Username	Problem	Language	Result	Execution time	Memory
736906		onlk97	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	208 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);
    int cnt=0;
    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 l=1,r=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;
    }
    return l;
}

Compilation message (stderr)

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

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