Submission #736478

#	Time	Username	Problem	Language	Result	Execution time	Memory
736478		puppy	Rarest Insects (IOI22_insects)	C++17	100 / 100	73 ms	576 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 + (r - l > 10) >> 1;
        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;
            }
        }
        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 {
            if ((m + 1) * S > N) return m;
            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:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         int m = l + r + 1 + (r - l > 10) >> 1;
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~
insects.cpp:36:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |         if (st.size() != m * S) {
      |             ~~~~~~~~~~^~~~~~~~

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