제출 #1281258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281258		Faggi	드문 곤충 (IOI22_insects)	C++20	0 / 100	5 ms	460 KiB

insects

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();

vector<bool> vis, en;
map<vector<bool>, ll> memo;
ll n;

void mi(ll x){ en[x]=1; }
void mo(ll x){ en[x]=0; }

ll pBtn(){
    if(memo.count(en)) return memo[en];
    for(ll i=0;i<sz(en);i++){
        if(vis[i]!=en[i]){
            if(vis[i]) move_outside(i);
            else move_inside(i);
            vis[i]=en[i];
        }
    }
    ll x=press_button();
    memo[vis]=x;
    return x;
}

int min_cardinality(int N){
    n=N;
    vis.assign(N,0);
    en.assign(N,0);

    vector<ll> in,out,ins;
    for(ll i=0;i<n;i++) ins.pb(i);

    mi(0);
    in.pb(0);
    ll act=1;
    for(auto k:ins){
        if(k==0) continue;
        mi(k);
        if(pBtn()>1){
            mo(k);
            out.pb(k);
        }else{
            in.pb(k);
            act++;
        }
    }

    ll tot=act;
    ll l=1, r=n/tot, pos=1;
    ins=out;

    while(l<=r){
        ll piv=(l+r+1)/2;
        in.clear();
        out.clear();

        ll act_now=tot;

        for(auto k:ins){
            mi(k);
            if(pBtn()>piv){
                mo(k);
                out.pb(k);
            }else{
                in.pb(k);
                act_now++;
            }
        }

        if(act_now==tot*piv){
            pos=piv;
            l=piv+1;
            ins=out;
        }else{
            r=piv-1;
            for(auto k:in) mo(k);
            ins=in;
        }
    }
    return int(pos);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75