Submission #793162

#	Time	Username	Problem	Language	Result	Execution time	Memory
793162		rnl42	Rarest Insects (IOI22_insects)	C++17	99.76 / 100	57 ms	456 KiB

insects

#include "insects.h"
#include <vector>
#include <iostream>
using namespace std;

int N, W;
vector<bool> deleted;
int remaining;

int get_width() {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        move_inside(i);
        if (press_button() >= 2) {
            move_outside(i);
        } else {
            deleted[i] = true;
            ret++;
        }
    }
    return ret;
}

int min_cardinality(int _N) {
    N = _N;
    deleted.resize(N);
    W = get_width();
    remaining = N-W;
    int mini = 1, maxi = N/W;
    int minh = 1, maxh = N-W+1;
    int only_insect = -1;
    if (W == 1) mini = N;
    while (mini != maxi) {
        int borne_sup = mini + remaining/W;
        maxi = min(maxi, borne_sup);
        int borne_inf = mini+max(remaining - (maxh-minh+1)*(W-1), 0);
        mini = max(mini, borne_inf);
        if (mini == maxi) break;

        int mid = mini+1 == maxi ? (mini+maxi+1)>>1 : (mini+maxi)>>1;
        vector<int> in_machine;
        vector<int> out_machine;
        bool first = true;
        for (int i = 0; i < N; i++) {
            if (!deleted[i]) {
                if (only_insect != i) { move_inside(i); }
                if (only_insect != i && press_button() > mid) {
                    move_outside(i);
                    out_machine.push_back(i);
                } else {
                    if (only_insect == i) only_insect = -1;
                    in_machine.push_back(i);
                }
                first = false;
            }
        }
        only_insect = -1;
        if (in_machine.size() == W*(mid-minh)) {
            for (int i : in_machine) {
                deleted[i] = true;
                remaining--;
            }
            mini = mid;
            minh = mid;
        } else {
            for (int i : out_machine) {
                deleted[i] = true;
                remaining--;
            }
            for (int i : in_machine) {
                if (only_insect == -1) only_insect = i;
                else move_outside(i);
            }
            maxi = mid-1;
            maxh = mid;
        }
    }
    return mini;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:58:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |         if (in_machine.size() == W*(mid-minh)) {
      |             ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
insects.cpp:43:14: warning: variable 'first' set but not used [-Wunused-but-set-variable]
   43 |         bool first = true;
      |              ^~~~~

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