제출 #1062737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062737		Zero_OP	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	39 ms	928 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 = (int)inside_insects.size();

    for(int i : inside_insects) move_outside(i);
    vector<int> greedy_insects = outside_insects;

    int ans = 1;
    while((int)greedy_insects.size() >= distinct_colors){
        int nInsects = (int)greedy_insects.size();
        int mid = ((nInsects / distinct_colors) + 1) / 2;

        vector<int> good, bad;
        for(int i = 0; i < nInsects; ++i){
            move_inside(greedy_insects[i]);
            if(press_button() > mid){
                bad.push_back(greedy_insects[i]);
                move_outside(greedy_insects[i]);
            } else{
                good.push_back(greedy_insects[i]);
            }
        }

        if(mid * distinct_colors == (int)good.size()){
            ans += mid;
            greedy_insects = bad;
        } else greedy_insects = good;

        if((int)greedy_insects.size() >= distinct_colors) for(int i : good) move_outside(i);
    }

    return ans;
}

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

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

    return 0;
}
#endif

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