oj.uz

Submission #1025049

# Submission time Handle Problem Language Result Execution time Memory
1025049 2024-07-16T14:50:49 Z vjudge1 Rarest Insects (IOI22_insects) C++17
0 / 100
 70 ms 696 KB 
#include "insects.h"
#include <bits/stdc++.h>

#define ll long long
#define sz(s) (int)s.size()
#define pb push_back
#define in insert
#define lb lower_bound
#define ub upper_bound

using namespace std;

const int MAX=2e5+10;

int n;
vector<int> a;
set<int> st;

bool check(int m){
    vector<int> vec;
    for(int i=0;i<n;i++){
        if(!st.count(i)){
            move_inside(i);
            if(press_button()>m){
                move_outside(i);
            }
            else{
                st.in(i);
                vec.pb(i);
            }
        }
    }
    if(sz(st)!=m*sz(a)){
        for(int x:vec)move_outside(x);
    }
    return (sz(st)==m*sz(a));
}

int min_cardinality(int N){
    n=N;
    for(int i=0;i<N;i++){
        move_inside(i);
        if(press_button()==2){
            move_outside(i);
        }
        else{
            a.pb(i);
            st.in(i);
        }
    }
    int l=1,r=N/sz(a),res=1;
    while(l<=r){
        int m=(l+r)/2;
        if(check(m)){
            l=m+1;
            res=m;
        }
        else r=m-1;
    }
    return res;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 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 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 696 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Incorrect 4 ms 436 KB Wrong answer.
13 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 1 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 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 696 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Incorrect 4 ms 436 KB Wrong answer.
13 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 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Correct 8 ms 344 KB Output is correct
9 Correct 29 ms 600 KB Output is correct
10 Partially correct 39 ms 692 KB Output is partially correct
11 Partially correct 70 ms 588 KB Output is partially correct
12 Correct 26 ms 344 KB Output is correct
13 Incorrect 52 ms 600 KB Wrong answer.
14 Halted 0 ms 0 KB -