Submission #1025049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025049		vjudge1	드문 곤충 (IOI22_insects)	C++17	0 / 100	70 ms	696 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;

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