Submission #799730

#	Time	Username	Problem	Language	Result	Execution time	Memory
799730		rnl42	Rarest Insects (IOI22_insects)	C++17	99.76 / 100	54 ms	420 KiB

insects

#include "insects.h"
#include <vector>
#include <iostream>
#include <random>
#include <algorithm>
#include <numeric>
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;
    if (W == 1) mini = N;
    vector<int> order(N);
    mt19937 rng(42);
    while (mini != maxi) {
        int mid = mini+1 == maxi ? (mini+maxi+1)>>1 : ((mini+maxi+(rng()&1))>>1);
        vector<int> in_machine;
        vector<int> out_machine;
        for (int i = 0; i < N; i++) {
            if (!deleted[i]) {
                move_inside(i);
                if (press_button() > mid) {
                    move_outside(i);
                    out_machine.push_back(i);
                } else {
                    in_machine.push_back(i);
                }
            }
        }
        if ((int)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) {
                move_outside(i);
            }
            maxi = mid-1;
            maxh = mid;
        }
    }
    return mini;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:34:19: warning: variable 'maxh' set but not used [-Wunused-but-set-variable]
   34 |     int minh = 1, maxh = N-W+1;
      |                   ^~~~

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