제출 #777514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777514		alexander707070	드문 곤충 (IOI22_insects)	C++17	0 / 100	1 ms	208 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;
        type[i]=i+1; br[i+1]=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() == int(diff.size()) );
            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[type[diff[r[i]]]]++;
    }

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

    return ans;
}

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