제출 #1224169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224169		Sharky	Rarest Insects (IOI22_insects)	C++20	99.95 / 100	17 ms	676 KiB

insects

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

void conv(set<int> a, set<int> b) {
    vector<int> er;
    for (auto& x : a) if (!b.count(x)) move_outside(x);
    for (auto& x : b) if (!a.count(x)) move_inside(x);
}

int conf;
set<int> cur;

int f = 2000;

int min_cardinality(int N) {
    set<int> base;
    for (int i = 0; i < N; i++) {
        move_inside(i);
        if (press_button() == 1) base.insert(i);
        else move_outside(i);
    }
    vector<bool> bye(N, 0);
    int sz = base.size();
    cur = base;
    int lo = 1, hi = N / sz;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        conv(cur, base);
        cur = base;
        vector<int> vt;
        for (int i = 0; i < N; i++) {
            if (cur.count(i) || bye[i]) continue;
            if (cur.size() == sz * mid) {
                vt.push_back(i);
                continue;
            }
            move_inside(i);
            if (press_button() <= mid) cur.insert(i);
            else {
                move_outside(i);
                vt.push_back(i);
            }
        }
        if (cur.size() == sz * mid) {
            base = cur;
            lo = mid;
        } else {
            for (auto& x : vt) bye[x] = 1;
            hi = (cur.size() / sz);
        }
    }
    return lo;
}

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