Submission #777516

#	Time	Username	Problem	Language	Result	Execution time	Memory
777516		alexander707070	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	336 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"
#define MAXN 2007
using namespace std;

int n,last,cnt,ans;
vector<int> diff,s;
int type[MAXN],l[MAXN],r[MAXN],br[MAXN];
bool used[MAXN],in[MAXN];
vector< pair<int,int> > qr;

int lg(int x){
    if(x==1)return 0;
    return lg(x/2)+1;
}

int min_cardinality(int N){
    n=N;

    for(int i=0;i<n;i++){
        move_inside(i);
        diff.push_back(i);

        if(press_button()>1){
            move_outside(i);
            diff.pop_back();
        }
    }

    for(int i:diff){
        used[i]=true; br[i]=1;
        move_outside(i);
    }

    for(int i=0;i<n;i++){
        if(!used[i]){
            l[i]=-1; r[i]=int(diff.size());
            s.push_back(i);
        }
    }

    for(int i=0;i<20;i++){

        qr.clear();
        for(int f:s){
            qr.push_back({(l[f]+r[f])/2,f});
        }
        sort(qr.begin(),qr.end());

        int pt=0;
        for(int f=0;f<n;f++){
            while(pt<=qr[f].first){
                move_inside(diff[pt]); pt++;
            }
            move_inside(qr[f].second);
            in[qr[f].second]=( press_button() == pt+1 );
            move_outside(qr[f].second);
        }

        for(int f=pt;f>=0;f--){
            move_outside(diff[f]);
        }

        for(int f:s){
            if(in[f]){
                r[f]=(l[f]+r[f])/2;
            }else{
                l[f]=(l[f]+r[f])/2;
            }
        }
    }

    for(int i:s){
        br[diff[r[i]]]++;
    }

    ans=n;
    for(int i:diff){
        ans=min(ans,br[i]);
    }

    return ans;
}

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