제출 #1230578

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

insects

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

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

vector<int> ord, cand;
int vis[2000], act = 0;

void get_in(int u) {
    u = ord[u];
    if(vis[u]) return ;
    act++;
    vis[u] = 1;
    move_inside(u);
}

void get_out(int u) {
    u = ord[u];
    if(!vis[u]) return ;
    act--;
    vis[u] = 0;
    move_outside(u);
}

int min_cardinality(int n) {
    ord = vector<int>(n);
    iota(ord.begin(), ord.end(), 0);
    shuffle(ord.begin(), ord.end(), rng);

    int l=2, r=n, ans=1;

    get_in(0);
    for(int i=1; i<n; i++) {
        get_in(i);
        if(press_button() == 2) {
            get_out(i);
            cand.push_back(i);
        } 
    }

    int D = act;
    r = n / D;
    while(l <= r) {
        int mid = (l + r) / 2;

        vector<int> L, R;
        for(int u : cand) {
            if(act == mid * D) break;
            get_in(u);

            if(press_button() == mid + 1) {
                get_out(u);
                L.push_back(u);
                continue;
            }

            R.push_back(u);
        }

        if(act == mid * D) {
            ans = mid;
            l = mid + 1;
            cand = L;
        } else {
            r = mid - 1;
            for(int u : R) get_out(u);
            cand = R;
        }
    }

    return ans;
}

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