Submission #634733

#	Time	Username	Problem	Language	Result	Execution time	Memory
634733		mosiashvililuka	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	222 ms	448 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"
using namespace std;
int BO[2009];
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[2009],fx[2009],p[2009],pi,lef,rig,mid;
void ins(int q){
    if(BO[q]==1) return;
    BO[q]=1;
    move_inside(q-1);
}
void outs(int q){
    if(BO[q]==0) return;
    BO[q]=0;
    move_outside(q-1);
}
int ask(){
    return press_button();
}
void clea(){
    for(int h=1; h<=a; h++){
        if(BO[h]==1){
            outs(h);
            BO[h]=0;
        }
    }
}
int min_cardinality(int N) {
    a=N;
    for(i=1; i<=a; i++){
        ins(i);
        if(ask()==2){
            outs(i);
            continue;
        }
        pi++;p[pi]=i;
    }
    clea();
    lef=0;rig=a/pi+1;
    while(1){
        if(lef+1>=rig) break;
        mid=(lef+rig)/2;zx=0;
        for(i=1; i<=a; i++){
            ins(i);zx++;
            if(ask()==mid+1){
                outs(i);zx--;
            }
        }
        clea();
        if(zx==mid*pi){
            lef=mid;
        }else{
            rig=mid;
        }
    }
    return lef;
}

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