Submission #686395

#	Time	Username	Problem	Language	Result	Execution time	Memory
686395		79brue	드문 곤충 (IOI22_insects)	C++17	0 / 100	1 ms	256 KiB

insects

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

using namespace std;

typedef long long ll;

int n;
int same[2002], par[2002], cnt[2002];
vector<int> ind;

int query(vector<int> &vec){
    static vector<int> recent (0);
    sort(recent.begin(), recent.end());
    sort(vec.begin(), vec.end());

    for(int i=0, j=0; i<(int)recent.size() || j<(int)vec.size(); ){
        if(i == (int)recent.size()) move_inside(vec[j++]-1);
        else if(j == (int)vec.size()) move_outside(vec[i++]-1);
        else if(recent[i] < vec[j]) move_outside(vec[i++]-1);
        else if(recent[i] > vec[j]) move_inside(vec[j++]-1);
        else i++, j++;
    }

    recent = vec;
    return press_button();
}

int min_cardinality(int N){
    n = N;
    for(int i=1; i<=n; i++){
        int l = 0, r = (int)ind.size()-1, key = (int)ind.size();
        while(l <= r){
            int m = (l+r)/2;
            vector<int> v (1, i);
            for(int j=0; j<=m; j++) v.push_back(ind[j]);
            if(query(v) == 2) key = m, r = m-1;
            else l = m+1;
        }
        if(key == (int)ind.size()) ind.push_back(i), par[i] = i, cnt[i] = 1;
        else par[i] = ind[key], cnt[ind[key]]++;
    }
    int ans = n;
    for(int i=1; i<=n; i++) if(cnt[i]) ans = min(ans, cnt[i]);
    return ans;
}

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