제출 #1024519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024519		vjudge1	드문 곤충 (IOI22_insects)	C++17	0 / 100	94 ms	748 KiB

insects

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75