Submission #1076357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076357		zsombor	Rarest Insects (IOI22_insects)	C++17	60.31 / 100	101 ms	1080 KiB

insects

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

int n, ans = 1e9;
vector<bool> b(2e3, false);
vector<int> v;
vector<bool> V(2e3, false);
vector<int> t(2e3, 0);
vector<int> cnt(2e3, 0);

void be(int i) {
    if (!b[i]) move_inside(i);
    b[i] = true;
}

void ki(int i) {
    if (b[i]) move_outside(i);
    b[i] = false;
}

int min_cardinality(int N) {
    n = N;
    for (int i = 0; i < n; i++) {
        be(i);
        if (press_button() == 1) {
            t[i] = v.size();
            v.push_back(i);
            V[i] = true;
        } else ki(i);
    }
    for (int j = 0; (1 << j) < v.size(); j++) {
        for (int i = 0; i < v.size(); i++) (i & (1 << j) ? be(v[i]) : ki(v[i]));
        for (int i = 0; i < n; i++) {
            if (V[i]) continue;
            be(i);
            t[i] += (press_button() - 1) * (1 << j);
            ki(i);
        }
    }
    for (int i = 0; i < n; i++) cnt[t[i]]++;
    for (int i = 0; i < v.size(); i++) ans = min(ans, cnt[i]);
    return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int j = 0; (1 << j) < v.size(); j++) {
      |                     ~~~~~~~~~^~~~~~~~~~
insects.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int i = 0; i < v.size(); i++) (i & (1 << j) ? be(v[i]) : ki(v[i]));
      |                         ~~^~~~~~~~~~
insects.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < v.size(); i++) ans = min(ans, cnt[i]);
      |                     ~~^~~~~~~~~~

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