제출 #684127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684127		sharaelong	드문 곤충 (IOI22_insects)	C++17	99.78 / 100	63 ms	448 KiB

insects

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

int uniq_cnt;

vector<int> cands;
vector<int> st;

void insert(int n, int p) {
    for (int x: cands) {
        move_inside(x);
        st.push_back(x);
        if (press_button() > p) {
            move_outside(x);
            st.pop_back();
        }
    }
}

void clear() {
    while (!st.empty()) {
        move_outside(st.back());
        st.pop_back();
    }
}

int min_cardinality(int n) {
    for (int i=0; i<n; ++i) cands.push_back(i);
    insert(n, 1);
    uniq_cnt = st.size();

    int low = 1, high = n / uniq_cnt;
    int offset = 0;
    while (low < high) {
        int mid = (low + high + 1) / 2;
        clear();
        insert(n, mid);
        if (st.size() == uniq_cnt * mid) {
            offset += mid;
            low = 0;
            high = high - mid;
            vector<int> tmp;
            for (int x: cands) {
                if (find(st.begin(), st.end(), x) == st.end()) tmp.push_back(x);
            }
            cands = tmp;
        } else {
            high = mid-1;
            cands = st;
        }
    }
    return low + offset;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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