제출 #1356164

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

insects

// Warning ChatGPT alert

#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){
        r = min(r, l + (int)a.size()/d);
        if(l==r) break;

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

        bool ok = 0;
        vector<int> best;

        for(int t=0;t<5;t++){
            vector<int> add;
            vector<int> cur=a;

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

            int tmp = tot;

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

            if(tmp==m*d){
                ok=1;
                best=add;
                tot=tmp;
                break;
            }

            // rollback
            for(auto x:add) move_outside(x);
        }

        if(ok){
            l=m;

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

    return l;
}

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