oj.uz

Submission #1062710

# Submission time Handle Problem Language Result Execution time Memory
1062710 2024-08-17T09:59:11 Z Zero_OP Rarest Insects (IOI22_insects) C++17
0 / 100
 142 ms 600 KB 
#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";
        assert(false);
    }

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

    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";
        assert(false);
    }

    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";
        assert(false);
    }

    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;
    }

    return res;
}

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

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

    return 0;
}
#endif

Compilation message

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Incorrect 5 ms 340 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Incorrect 5 ms 340 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Partially correct 1 ms 344 KB Output is partially correct
7 Partially correct 142 ms 440 KB Output is partially correct
8 Correct 9 ms 440 KB Output is correct
9 Partially correct 87 ms 344 KB Output is partially correct
10 Partially correct 73 ms 600 KB Output is partially correct
11 Partially correct 128 ms 344 KB Output is partially correct
12 Correct 14 ms 600 KB Output is correct
13 Partially correct 106 ms 444 KB Output is partially correct
14 Partially correct 70 ms 344 KB Output is partially correct
15 Incorrect 100 ms 592 KB Wrong answer.
16 Halted 0 ms 0 KB -