제출 #637085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637085		someone	드문 곤충 (IOI22_insects)	C++17	0 / 100	1 ms	304 KiB

insects

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

deque<int> act, nex, in;

int getMin(int nbType) {
    int n = act.size();
    if(nbType == 1)
        return n;
    if(nbType > n)
        return 0;

    int del = (int)ceil(0.38 * (double)n / (double)nbType);
    for(int i = 0; i < n; i++) {
        move_inside(act[i]);
        if(press_button() == del+1) {
            move_outside(act[i]);
            nex.push_back(act[i]);
        } else {
            in.push_back(act[i]);
        }
    }
    if((int)in.size() == del * nbType) {
        swap(act, nex);
        for(int i : in)
            move_outside(i);
        in.clear();
        nex.clear();
        return del + getMin(nbType);
    }
    for(int i : in)
        move_outside(i);

    deque<int> repr, garde;
    for(int i : nex) {
        move_inside(i);
        if(press_button() == 1) {
            repr.push_back(i);
        } else {
            move_outside(i);
            garde.push_back(i);
        }
    }
    for(int i : in) {
        move_inside(i);
        if(press_button() == 1)
            garde.push_back(i);
        move_outside(i);
    }
    for(int i : repr)
        move_outside(i);

    swap(garde, act);

    garde.clear();
    nex.clear();
    in.clear();
    return getMin(nbType - (int)repr.size());
}

int min_cardinality(int N) {
    int nbType = 0;
    for(int i = 0; i < N; i++)
        act.push_back(i);

    for(int i = 0; i < N; i++) {
        move_inside(i);
        if(press_button() == 2) {
            move_outside(i);
            nex.push_back(i);
        } else {
            nbType++;
            in.push_back(i);
        }
    }

    for(int i : in)
        move_outside(i);
    swap(act, nex);
    nex.clear();
    in.clear();

    return getMin(nbType) + 1;
}

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