Submission #1168853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168853		SmuggingSpun	Rarest Insects (IOI22_insects)	C++20	59.34 / 100	39 ms	492 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"
using namespace std;
template<class T>void minimize(T& a, T b){
    if(a > b){
        a = b;
    }
}
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
int min_cardinality(int n){
    vector<int>parent(n), size(n);
    iota(parent.begin(), parent.end(), 0);
    fill(size.begin(), size.end(), 1);
    auto find_set = [&] (int N){
        while(N != parent[N]){
            N = parent[N] = parent[parent[N]];
        }
        return N;
    };
    auto merge = [&] (int u, int v){
        if((u = find_set(u)) != (v = find_set(v))){
            if(size[u] < size[v]){
                swap(u, v);
            }
            size[parent[v] = u] += size[v];
        }
    };
    vector<int>d, s, low, high, p;
    for(int i = 0; i < n; i++){
        move_inside(i);
        if(press_button() == 2){
            move_outside(i);
            s.emplace_back(i);
            low.emplace_back(0);
            high.emplace_back(int(d.size()) - 1);
        }
        else{
            d.emplace_back(i);
        }
    }
    p.resize(s.size());
    int cur_pos = int(d.size()) - 1;
    while(true){
        int min_low = n, max_high = -1;
        vector<vector<int>>query(d.size());
        for(int i = 0; i < s.size(); i++){
            if(low[i] <= high[i]){
                int mid = (low[i] + high[i]) >> 1;
                minimize(min_low, low[i]);
                maximize(max_high, high[i]);
                query[mid].emplace_back(i);
            }
        }
        if(max_high == -1){
            break;
        }
        if(cur_pos >= max_high){
            for(int i = cur_pos; i >= min_low; move_outside(d[i--])){
                for(int& j : query[i]){
                    move_inside(s[j]);
                    if(press_button() == 2){
                        p[j] = d[i];
                        high[j] = i - 1;
                    }
                    else{
                        low[j] = i + 1;
                    }
                    move_outside(s[j]);
                }
            }
            cur_pos = min_low - 1;
        }
        else{
            for(int i = cur_pos + 1; i <= max_high; i++){
                move_inside(d[i]);
                for(int& j : query[i]){
                    move_inside(s[j]);
                    if(press_button() == 2){
                        p[j] = d[i];
                        high[j] = i - 1;
                    }
                    else{
                        low[j] = i + 1;
                    }
                    move_outside(s[j]);
                }
            }
            cur_pos = max_high;
        }
    }
    for(int i = 0; i < s.size(); i++){
        merge(s[i], p[i]);
    }
    int ans = n;
    for(int i = 0; i < n; i++){
        minimize(ans, size[find_set(i)]);
    }
    return ans;
}

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