Submission #851833

#	Time	Username	Problem	Language	Result	Execution time	Memory
851833		kh0i	Rarest Insects (IOI22_insects)	C++17	100 / 100	35 ms	1948 KiB

insects

#include <bits/stdc++.h>

#include "insects.h"
using namespace std;

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

set<int> inside;
map<int, set<int>> states;
int D = 0;
vector<int> a;

void move_in(int x){
    if(inside.count(x)) return;
    move_inside(a[x]);
    inside.insert(x);
}

void move_out(int x){
    if(!inside.count(x)) return;
    move_outside(a[x]);
    inside.erase(x);
}

int min_cardinality(int N) {
    a.resize(N);
    iota(a.begin(), a.end(), 0);
    shuffle(a.begin(), a.end(), rng);

    for (int i = 0; i < N; ++i) {
        D += 1;
        move_in(i);
        if (press_button() > 1) {
            move_out(i);
            D -= 1;
        }
    }
    states[1] = inside;
    for(int i = 0 ; i < N; ++i) states[N].insert(i);
    // clear
    for (int i = 0; i < N; ++i)
        move_out(i);

    // N log N
    int l = 1, r = N / D, ans = 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        vector<int> last_inserted;
        auto it = *states.lower_bound(mid);
        for (int i : it.second) {
            if ((int)inside.size() >= mid * D) break;
            if (!inside.count(i)) {
                move_in(i);
                if (press_button() > mid)
                    move_out(i); 
                else
                    last_inserted.push_back(i);
            }
        }
        cerr << "(cnt = " << inside.size() << ", mid = " << mid << ", d = " << D << ")\n";
        states[mid] = inside;
        if ((int)inside.size() >= mid * D) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
            for(int i : last_inserted) move_out(i);
        }
    }
    return ans;
}

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