Submission #799735

#	Time	Username	Problem	Language	Result	Execution time	Memory
799735		rnl42	Rarest Insects (IOI22_insects)	C++17	99.91 / 100	59 ms	544 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 r = rng()%6;
        int mid = maxi-mini > 5 ? (mini+maxi-1>>1)+(r >= 4 ? r-3 : r) : (mini+maxi+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:40:45: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   40 |         int mid = maxi-mini > 5 ? (mini+maxi-1>>1)+(r >= 4 ? r-3 : r) : (mini+maxi+1)>>1;
      |                                    ~~~~~~~~~^~
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.91 / 75