Submission #736472

#	Time	Username	Problem	Language	Result	Execution time	Memory
736472		puppy	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	70 ms	428 KiB

insects

#include "insects.h"
#include <vector>
#include <set>
#include <iostream>
using namespace std;
int dc[2005];
//1: 계속 넣을 것, 2: 계속 뺄 것
int min_cardinality(int N) {
    set<int> st;
    for (int i = 0; i < N; i++) {
        move_inside(i);
        st.insert(i);
        if (press_button() > 1) {
            move_outside(i);
            st.erase(i);
        }
        else {
            dc[i] = 1; //계속 넣고 있을 것
        }
    }
    int S = st.size(); //총 종류 수
    int l = 1, r = N / S;
    while (l < r) {
        int m = l + r + 1 >> 1;
        //답이 m 미만인지 체크
        for (int i = 0; i < N; i++) {
            if (dc[i] == 1 || dc[i] == 2) continue;
            move_inside(i);
            st.insert(i);
            if (press_button() > m) {
                move_outside(i);
                st.erase(i);
            }
            else {
                dc[i] = 3; //2: 일단 넣고 있는 것
            }
        }
        if (st.size() != m * S) {
            r = m - 1;
            //뺀 것들은 다시 안 넣을 것
            for (int i = 0; i < N; i++) {
                if (dc[i] == 0) dc[i] = 2;
                else if (dc[i] == 3) dc[i] = 0;
            }
        }
        else {
            l = m;
            for (int i = 0; i < N; i++) {
                if (dc[i] == 3) dc[i] = 1;
            }
        }
        for (int i = 0; i < N; i++) {
            if (dc[i] != 1 && dc[i] != 2 && st.find(i) != st.end()) {
                st.erase(i);
                move_outside(i);
            }
        }
    }
    return l;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:24:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         int m = l + r + 1 >> 1;
      |                 ~~~~~~^~~
insects.cpp:38:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         if (st.size() != m * S) {
      |             ~~~~~~~~~~^~~~~~~~

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