Submission #634588

#	Time	Username	Problem	Language	Result	Execution time	Memory
634588		mosiashvililuka	Rarest Insects (IOI22_insects)	C++17	60.36 / 100	163 ms	592 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;
vector <int> vv;
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;
        }
    }
}
void rec(int q, int w, vector <int> vv){
    int i;
    if(vv.size()==0) return;
    if(q==w){
        for(vector <int>::iterator it=vv.begin(); it!=vv.end(); it++){
            f[(*it)]=p[q];
        }
        return;
    }
    int mid=(q+w)/2;
    for(i=q; i<=mid; i++){
        ins(p[i]);
    }
    vector <int> qw,we;
    for(vector <int>::iterator it=vv.begin(); it!=vv.end(); it++){
        ins((*it));
        if(ask()==2){
            qw.push_back((*it));
        }else{
            we.push_back((*it));
        }
        outs((*it));
    }
    //clea();
    if(q==mid){
        clea();
    }else{
        int MID=(q+mid)/2;
        for(i=MID+1; i<=mid; i++){
            outs(p[i]);
        }
    }
    rec(q,mid,qw);
    clea();
    rec(mid+1,w,we);
}
int min_cardinality(int N) {
    a=N;
    for(i=1; i<=a; i++){
        ins(i);
        if(ask()==2){
            outs(i);
            vv.push_back(i);
            continue;
        }
        pi++;p[pi]=i;
        f[i]=i;
    }
    clea();
    rec(1,pi,vv);
    /*for(i=1; i<=a; i++) cout<<f[i]<<" ";
    cout<<"\n";
    return 2300;*/
    for(i=1; i<=a; i++){
        fx[f[i]]++;
    }
    zx=a+2;
    for(i=1; i<=a; i++){
        if(fx[i]==0) continue;
        zx=min(zx,fx[i]);
    }
    return zx;
}

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