Submission #634763

#	Time	Username	Problem	Language	Result	Execution time	Memory
634763		mosiashvililuka	Rarest Insects (IOI22_insects)	C++17	99.56 / 100	62 ms	428 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"
using namespace std;
int BO[2009],NO[2009],K[2009];
deque <int> de;
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;
        while(de.size()) de.pop_front();
        for(i=1; i<=a; i++) K[i]=0;
        for(i=1; i<=a; i++){
            if(NO[i]!=0){
                if(NO[i]==1) zx++;
                continue;
            }
            if(BO[i]==0){
                de.push_back(i);K[i]=1;
            }
            ins(i);zx++;
            if(ask()==mid+1){
                if(BO[i]==1){
                    de.pop_back();K[i]=2;
                }
                outs(i);zx--;
            }
        }
        //clea();
        if(zx==mid*pi){
            lef=mid;
            for(i=1; i<=a; i++){
                if(K[i]==1){
                    NO[i]=1;
                }
            }
        }else{
            rig=mid;
            for(i=1; i<=a; i++){
                if(K[i]==2) NO[i]=2;
            }
            while(de.size()){
                outs(de.back());
                de.pop_back();
            }
        }
    }
    return lef;
}

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