제출 #634202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634202		spacewalker	드문 곤충 (IOI22_insects)	C++17	99.79 / 100	65 ms	500 KiB

insects

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

using namespace std;

int ceil(int n, int r) {
    return n/r + n%r;
}

// Get an array of insects, such that all their types are distinct
// The representatives are left inside the machine
vector<int> getRepresentatives(int N) {
    vector<int> inMachine;
    for (int i = 0; i < N; ++i) {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
        } else {
            inMachine.push_back(i);
        }
    }
    return inMachine;
}

// find the max k such that all types have at least >= k insects
// in a query, we can check if all types have at least >= k' insects

int getAllLowerBound(vector<int> ids, int B, int answerMax, int machineBase) {
    if (answerMax == 0 || ids.size() < B) return 0; // base case
    if (ids.size() == 1) return (B == 1 ? 1 : 0);
    if (B == 1) return ids.size();
    /*
        printf("GALB([");
        for (int v : ids) printf("%d ", v);
        printf("], %d, %d)\n",B, answerMax);
    */
    // set mid such that the success case eliminates around N/2 elements
    // int mid = ceil(ids.size()/2, B);
    int mid = ids.size() / (2 * B) + 1;
    if (mid > answerMax) mid = answerMax;
    set<int> inMachine;
    for (int v : ids) {
        move_inside(v);
        if (press_button() > machineBase + mid) {
            // this is the >midth insect of its type, keep it out
            move_outside(v);
        } else {
            inMachine.insert(v);
        }
    }
    // printf("%lu in machine\n", inMachine.size());
    if (inMachine.size() >= mid * B) {
        // check success; do a GALB on the rest now
        vector<int> remaining;
        for (int v : ids) if (inMachine.count(v) == 0) remaining.push_back(v);
        return mid + getAllLowerBound(remaining, B, answerMax - mid, machineBase + mid);
    } else {
        // check fail; do a GALB with a lower ansMax
        // note that it suffices to only use the ones in the machine
        for (int v : inMachine) move_outside(v);
        vector<int> machinev(begin(inMachine), end(inMachine));
        return getAllLowerBound(machinev, B, mid - 1, machineBase);
    }
}

int min_cardinality(int N) {
    vector<int> reps = getRepresentatives(N);
    int B = reps.size(); // B is the number of types
    // printf("! %d unique types\n", B);
    vector<int> insects;
    set<int> inReps(begin(reps), end(reps));
    for (int i = 0; i < N; ++i) {
        if (inReps.count(i) == 0) insects.push_back(i);
    }
    return getAllLowerBound(insects, B, N/B - 1, 1) + 1;
}

컴파일 시 표준 에러 (stderr) 메시지

insects.cpp: In function 'int getAllLowerBound(std::vector<int>, int, int, int)':
insects.cpp:29:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     if (answerMax == 0 || ids.size() < B) return 0; // base case
      |                           ~~~~~~~~~~~^~~
insects.cpp:52:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |     if (inMachine.size() >= mid * B) {
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~

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