Submission #1084406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084406		SamueleVid	Rarest Insects (IOI22_insects)	C++17	10 / 100	250 ms	448 KiB

insects

#include <bits/stdc++.h>
using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();

int min_cardinality(int N) {
    
    vector<int> type(N, -1);
    for (int i = 0; i < N; i ++) {
        if (type[i] != -1) continue;
        type[i] = i;
        stack<int> dentro;
        dentro.push(i);
        move_inside(i);
        for (int j = i + 1; j < N; j ++) {
            dentro.push(j);
            move_inside(j);
            if (press_button() < dentro.size()) {
                move_outside(j);
                dentro.pop();
            }
            else {
                type[j] = i;
            }
        }
        while (!dentro.empty()) {
            move_outside(dentro.top()); dentro.pop();
        }

    }

    // cout << "types : " << '\n';
    // for (auto x : type) cout << x << " ";
    // cout << '\n';

    map<int, int> numero_types;
    for (auto x : type) numero_types[x] ++;
    int minore = 1e9;
    for (auto [_, x] : numero_types) minore = min(minore, x);

    return minore;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:20:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::stack<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |             if (press_button() < dentro.size()) {
      |                 ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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