Submission #684130

#	Time	Username	Problem	Language	Result	Execution time	Memory
684130		sharaelong	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	62 ms	428 KiB

insects

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

int uniq_cnt;

vector<int> cands;
vector<int> st;
int cnt = 0;

void insert(int n, int p) {
    for (int x: cands) {
        if (cnt < p && find(st.begin(), st.end(), x) != st.end()) continue;
        move_inside(x);
        st.push_back(x);
        if (press_button() > p) {
            move_outside(x);
            st.pop_back();
        }
    }
    cnt = p;
}

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;
        if (cnt >= mid) 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;
}

Compilation message (stderr)

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

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