Submission #736466

#	Time	Username	Problem	Language	Result	Execution time	Memory
736466		puppy	Rarest Insects (IOI22_insects)	C++17	0 / 100	67 ms	492 KiB

insects

#include "insects.h"
#include <vector>
#include <set>
#include <iostream>
using namespace std;
int dc[2005];
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) continue;
            move_inside(i);
            st.insert(i);
            if (press_button() > m) {
                move_outside(i);
                st.erase(i);
            }
            else {
                dc[i] = 2; //2: 일단 넣고 있는 것
            }
        }
        if (st.size() != m * S) {
            r = m - 1;
            for (int i = 0; i < N; i++) {
                if (dc[i] == 2) dc[i] = 0;
                else if (dc[i] == 0) dc[i] = 1;
            }
        }
        else {
            l = m;
            for (int i = 0; i < N; i++) {
                if (dc[i] == 2) dc[i] = 1;
            }
        }
    }
    return l;
}

Compilation message (stderr)

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

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