Submission #634179

#	Time	Username	Problem	Language	Result	Execution time	Memory
634179		spacewalker	Rarest Insects (IOI22_insects)	C++17	82.27 / 100	116 ms	640 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) return 0; // base case
    /*
        printf("GALB([");
        for (int v : ids) printf("%d ", v);
        printf("], %d, %d)\n",B, answerMax);
    */
    int mid = answerMax - 4 * answerMax / 5; // this is a guess
    // printf("checking if min >= %d\n", mid);
    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, ceil(N, B) - 1, 1) + 1;
}

Compilation message (stderr)

insects.cpp: In function 'int getAllLowerBound(std::vector<int>, int, int, int)':
insects.cpp:48:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     if (inMachine.size() >= mid * B) {
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~

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