Submission #686416

#	Time	Username	Problem	Language	Result	Execution time	Memory
686416		79brue	Rarest Insects (IOI22_insects)	C++17	61.06 / 100	155 ms	484 KiB

insects

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

using namespace std;

typedef long long ll;

int n, k;
vector<int> vec;
bool isFirst[2002];
int type[2002], cnt[2002];
bool inside[2002];

void dnc(int l, int r, vector<int> &candidates){
    if(candidates.empty()) return;
    if(l==r){
        for(auto x: candidates) type[x] = vec[l];
        return;
    }
    int m = (l+r)/2;
    for(int i=l; i<=m; i++) if(!inside[vec[i]]) inside[vec[i]] = 1, move_inside(vec[i]);
    for(int i=m+1; i<=r; i++) if(inside[vec[i]]) inside[vec[i]] = 0, move_outside(vec[i]);

    vector<int> vecL, vecR;
    for(auto x: candidates){
        move_inside(x);
        if(press_button() == 2) vecL.push_back(x);
        else vecR.push_back(x);
        move_outside(x);
    }

    dnc(l, m, vecL);
    dnc(m+1, r, vecR);
}

int min_cardinality(int N){
    n = N;

    /// 종류 알아내기
    for(int i=0; i<n; i++){
        move_inside(i);
        if(press_button() == 2) move_outside(i);
        else vec.push_back(i), isFirst[i] = 1, inside[i] = 1, type[i] = i;
    }

    /// dnc 하기
    k = (int)vec.size();
    vector<int> notFirst;
    for(int i=0; i<n; i++) if(!isFirst[i]) notFirst.push_back(i);
    dnc(0, k-1, notFirst);

    for(int i=0; i<n; i++) cnt[type[i]]++;
    int ans = INT_MAX;
    for(int i=0; i<n; i++) ans = min(ans, cnt[type[i]]);
    return ans;
}

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