oj.uz

Submission #1024519

# Submission time Handle Problem Language Result Execution time Memory
1024519 2024-07-16T06:51:52 Z vjudge1 Rarest Insects (IOI22_insects) C++17
0 / 100
 94 ms 748 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;

vector<int> a;
int cnt[MAX];
set<int> st;

void solve(int l,int r,vector<int> b){
    if(b.empty())return;
    if(l==r){
        // cout<<l<<" "<<r<<" ";
        // for(int x:b)cout<<x<<" ";
        // cout<<"\n";
        cnt[l]+=sz(b);
        return;
    }
    int m=(l+r)/2;
    while(st.ub(m)!=st.end()&&*st.ub(m)<=r){
        move_outside(*st.ub(m));
        st.erase(st.ub(m));
    }
    vector<int> L,R;
    for(int i=l;i<=m;i++){
        if(!st.count(i))move_inside(i);
        st.in(i);
    }
    for(int i:b){
        move_inside(i);
        if(press_button()==2)L.pb(i);
        else R.pb(i);
        move_outside(i);
    }
    solve(l,m,L);
    solve(m+1,r,R);
}

int min_cardinality(int N){
    vector<int> b;
    for(int i=0;i<N;i++){
        move_inside(i);
        if(press_button()==2){
            b.pb(i);
            move_outside(i);
        }
        else{
            // cout<<i<<"\n";
            st.in(i);
            a.pb(i);
        }
    }
    solve(0,sz(a)-1,b);
    int ans=N;
    for(int i=0;i<sz(a);i++)ans=min(ans,cnt[i]+1);
    return ans;
}

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 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Incorrect 4 ms 452 KB Wrong answer.
9 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 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Incorrect 4 ms 452 KB Wrong answer.
9 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 11 ms 600 KB Output is correct
8 Correct 14 ms 344 KB Output is correct
9 Incorrect 94 ms 748 KB Wrong answer.
10 Halted 0 ms 0 KB -