제출 #1024778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024778		vjudge1	드문 곤충 (IOI22_insects)	C++17	49.40 / 100	153 ms	1276 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;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l,int r){
    return rng()%(r-l+1)+l;
}

void solve(int l,int r,vector<int> b){
    if(b.empty())return;
    if(l==r){
        cnt[l]+=sz(b);
        return;
    }
    int m=rnd(l,r);
    while(st.ub(m)!=st.end()&&*st.ub(m)<=r){
        move_outside(a[*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(a[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{
            st.in(sz(a));
            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: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 24.4 / 75