Submission #658470

#	Time	Username	Problem	Language	Result	Execution time	Memory
658470		coding_snorlax	Rarest Insects (IOI22_insects)	C++17	99.35 / 100	72 ms	456 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int All_type[2000]={0};
int Box[2000]={0};
int Check[2000]={0};
int All_possible[2000];
int Total_N;
int level_1;
int check(int Num){
    //cout<<Total_N<<"Total_N"<<endl;
    int tmp;
    for(int j=0;j<Total_N;j++){
        //cout<<"All_possible "<<All_possible[j]<<" Check "<<Check[j]<<endl;
        if(All_possible[j] && !Check[j]){
            //cout<<j<<endl;
            move_inside(j);
            tmp=press_button();
            if(tmp>Num){
                move_outside(j);
            }
            else{
                //now_active
                Check[j]=2;
            }
        }
    }
    int Count=0;
    for(int j=0;j<Total_N;j++){
        if(Check[j]) {
            Count++;
        }
    }
    if(Count<level_1*Num){
        for(int j=0;j<Total_N;j++){
            if(Check[j]==2){
                move_outside(j);
                Check[j]=0;
            }
            else if(!Check[j]) All_possible[j]=0;
        }
        return 0;
    }
    for(int j=0;j<Total_N;j++){
        if(Check[j]==2){
            Check[j]=1;
        }
    }
    return 1;
 
}
int min_cardinality(int N){
    Total_N=N;
    for(int j=0;j<N;j++){
        All_possible[j]=1;
    }
    for(int j=0;j<N;j++){
        int tmp;
        if(!All_type[j]){
            move_inside(j);
            tmp=press_button();
            if(tmp>1){
                move_outside(j);
            }
            else{
                Check[j]=1;
            }
        }
    }
    int Count=0;
    for(int j=0;j<N;j++){
        if(Check[j]==1) {
            move_outside(j);
            Check[j]=0;
            Count++;
        }
    }
    level_1=Count;
    //binary_search
    int L=1,R=N/level_1+1;
    while(L!=R){
        if((R-L)<=2){
            if(check(L+1)){
                if(check(L+2)) return L+2;
                return L+1;
            }
            return L;
        }
        int M=(L+R)/2;
        if(check(M)) L=M;
        else R=M+1;
    }
    return L;
}

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