Submission #826338

#	Time	Username	Problem	Language	Result	Execution time	Memory
826338		alvingogo	Rarest Insects (IOI22_insects)	C++17	100 / 100	52 ms	456 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;

struct DSU{
    vector<int> bo;
    void init(int x){
        bo.resize(x);
        iota(bo.begin(),bo.end(),0);
    }
    int find(int x){
        return bo[x]==x?bo[x]:bo[x]=find(bo[x]);
    }
    void merge(int x,int y){
        x=find(x);
        y=find(y);
        bo[x]=y;
    }
}dsu;
int min_cardinality(int n) {
    int cnt=0;
    dsu.init(n);
    vector<int> vis(n);
    vector<int> bo(n);
    for(int i=0;i<n;i++){
        move_inside(i);
        int a=press_button();
        if(a>1){
            move_outside(i);
        }
        else{
            vis[i]=1;
            cnt++;
        }
    }
    if(cnt==1){
        return n;
    }
    if(cnt<=3){
        vector<int> cg;
        for(int w=0;w<cnt;w++){
            int k=1;
            vector<int> vz(n);
            for(int i=0;i<n;i++){
                if(!vis[i]){
                    move_inside(i);
                    int a=press_button();
                    if(a==k){
                        move_outside(i);
                    }
                    else{
                        vz[i]=1;
                        k=a;
                    }
                }
            }
            for(int i=0;i<n;i++){
                if(vz[i]){
                    vis[i]=1;
                    move_outside(i);
                }
            }
            cg.push_back(k);
        }
        return *min_element(cg.begin(),cg.end());
    }
    else{
        int l=1,r=(n-1)/cnt+3;
        int cc=cnt;
        while(r>l){
            int m=(l+r)/2;
            vector<int> pu(n);
            for(int i=0;i<n;i++){
                if(!vis[i]){
                    move_inside(i);
                    cc++;
                    int a=press_button();
                    if(a>m){
                        move_outside(i);
                        cc--;
                    }
                    else{
                        pu[i]=1;
                    }
                }
            }
            if(m*cnt!=cc){
                r=m;
                for(int i=0;i<n;i++){
                    if(pu[i]){
                        move_outside(i);
                        cc--;
                    }
                    else{
                        vis[i]=1;
                    }
                }
            }
            else{
                l=m+1;
                for(int i=0;i<n;i++){
                    if(pu[i]){
                        vis[i]=1;
                    }
                }
            }
        }
        return l-1;
    }
}

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