제출 #826330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826330		alvingogo	Rarest Insects (IOI22_insects)	C++17	99.91 / 100	60 ms	324 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<=0){
        int cc=cnt;
        vector<int> vz;
        for(int i=0;i<n;i++){
            if(!vis[i]){
                move_inside(i);
                cc++;
                if(1){
                    move_outside(i);
                    cc--;
                }
                else{
                
                }
            }
        }
    }
    else{
        int l=1,r=(n-1)/cnt+2;
        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;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:25:22: warning: control reaches end of non-void function [-Wreturn-type]
   25 |     vector<int> vis(n);
      |                      ^

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