제출 #1182316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182316		PagodePaiva	Rarest Insects (IOI22_insects)	C++20	50.07 / 100	39 ms	504 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 2010;
int cnt[N];
vector <int> rep;

void solve(int l, int r, vector <int> ask){
    if(l == r){
        cnt[rep[l]] = ask.size()+1;
        return;
    }
    vector <int> v1, v2;
    int mid = (l+r)/2;
    for(int i = mid+1;i <= r;i++){
        move_outside(rep[i]);
    }
    for(auto x : ask){
        move_inside(x);
        int val = press_button();
        move_outside(x);
        if(val > 1) v1.push_back(x);
        else v2.push_back(x);
    }
    solve(l, mid, v1);
    for(int i = l;i <= r;i++){
        if(i <= mid){
            move_outside(rep[i]);
        }
        else{
            move_inside(rep[i]);
        }
    }
    solve(mid+1, r, v2);
    return;
}

int min_cardinality(int n) {
    rep.push_back(0);
    move_inside(0);
    vector <int> at;
    for(int i = 1;i < n;i++){
        move_inside(i);
        int v = press_button();
        if(v > 1) {
            move_outside(i);
            at.push_back(i);
        }
        else{
            rep.push_back(i);
        }
    }
    solve(0, rep.size()-1,at);
    int ans = 1e9;
    for(auto x : rep){
        //cout << cnt[x] << ' ';
        ans = min(ans, cnt[x]);
    }
    return ans;
}

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