제출 #1356162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356162		charlesti	드문 곤충 (IOI22_insects)	C++20	53.16 / 100	38 ms	464 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

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

int min_cardinality(int n){
    vector<int> a,b;
    for(int i=0;i<n;i++) a.push_back(i);

    // D
    for(int i=0;i<n;i++){
        move_inside(i);
        if(press_button()>1) move_outside(i);
        else b.push_back(i);
    }

    int d = b.size();

    vector<int> u(n,0), na;
    for(auto x:b) u[x]=1;
    for(auto x:a) if(!u[x]) na.push_back(x);
    a = na;

    int l=1, r=n/d;
    int tot=d;

    while(l<r){
        int m=(l+r+1)/2;

        vector<int> add;
        vector<int> cur=a;

        shuffle(cur.begin(),cur.end(),rng);

        for(auto x:cur){
            move_inside(x);
            tot++;
            if(press_button()>m){
                move_outside(x);
                tot--;
            }
            else{
                add.push_back(x);
            }
            if(tot==m*d) break;
        }

        if(tot==m*d){
            l=m;

            vector<int> mark(n,0), nxt;
            for(auto x:add) mark[x]=1;
            for(auto x:a) if(!mark[x]) nxt.push_back(x);
            a=nxt;
        }
        else{
            r=m-1;
            for(auto x:add){
                move_outside(x);
                tot--;
            }
        }
    }

    return l;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 15 / 15
• 서브태스크 3: 28.16 / 75