Submission #1062718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062718		Zero_OP	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	152 ms	1048 KiB

insects

#include<bits/stdc++.h>
#ifndef LOCAL
    #include<insects.h>
#endif

using namespace std;

#ifdef LOCAL
const int MAX = 2e3 + 5;
int N;
int press[MAX];
vector<int> ar;
bool in[MAX];
int cnt[MAX]; //for testcase, use value <= 2000
multiset<int> st;

void move_inside(int i){
    ++press[0];
    if(press[0] > 40000){
        cout << "Too much operations move_inside!\n";
        exit(0);
    }

    if(in[i]) {
        cout << "Already added!\n";
        exit(0);
    }

    in[i] = true;
    if(cnt[ar[i]]) st.erase(st.find(cnt[ar[i]]));
    cnt[ar[i]] += 1;
    st.insert(cnt[ar[i]]);
}

void move_outside(int i){
    ++press[1];
    if(press[1] > 40000){
        cout << "Too much operations move_outside!\n";
        exit(0);
    }

    if(!in[i]){
        cout << "Not added yet!\n";
        exit(0);
    }

    in[i] = false;
    if(cnt[ar[i]]) st.erase(st.find(cnt[ar[i]]));
    cnt[ar[i]] -= 1;
    st.insert(cnt[ar[i]]);
}

int press_button(){
    ++press[2];
    if(press[2] > 40000){
        cout << "Too much operations press_button!\n";
        exit(0);
    }

    if(st.empty()){
        cout << "No insects!\n";
        assert(false);
    }

    return *prev(st.end());
}
#endif

int min_cardinality(int N){
    vector<int> inside_insects, outside_insects;
    for(int i = 0; i < N; ++i){
        move_inside(i);
        if(press_button() > 1){
            outside_insects.push_back(i);
            move_outside(i);
        } else inside_insects.push_back(i);
    }

    if(outside_insects.empty()) return 1;

    int distinct_colors = inside_insects.size();
    for(int i : inside_insects) move_outside(i);

    int l = 2, r = N / distinct_colors, res = 1;
    while(l <= r){
        int mid = l + r >> 1;
        
        vector<int> keep;
        for(int i = 0; i < N; ++i){
            move_inside(i);
            if(press_button() > mid){
                move_outside(i);
            } else keep.push_back(i); 
        }

        if(keep.size() == distinct_colors * mid){
            res = mid;
            l = mid + 1;
        } else r = mid - 1;

        for(int i : keep) move_outside(i);
    }

    return res;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N = 6;
    ar = {5, 5, 9, 9, 9, 9};
    cout << min_cardinality(N);

    return 0;
}
#endif

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = l + r >> 1;
      |                   ~~^~~
insects.cpp:96:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |         if(keep.size() == distinct_colors * mid){
      |            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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