제출 #736916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736916		onlk97	드문 곤충 (IOI22_insects)	C++17	47.50 / 100	186 ms	508 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;
    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;
}

컴파일 시 표준 에러 (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: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 22.5 / 75