Submission #1234120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234120		trimkus	Rarest Insects (IOI22_insects)	C++20	50.02 / 100	54 ms	436 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
    vector<int> ord(N);
    iota(begin(ord), end(ord), 0);
    mt19937 rng(1);
    shuffle(begin(ord), end(ord), rng);
    vector<bool> vis(N);
    int inside = 0;
    int diff = 0;
    vector<int> took;
    auto calc = [&](int till, bool first = false) -> void {
      for (int i : ord) {
        if (vis[i]) continue;
          move_inside(i);
          if (press_button() > till) {
            move_outside(i);
          } else {
            took.push_back(i);
            inside += 1;
            vis[i] = 1;
            if (first) diff += 1;
          }
      }
    };
    calc(1, true);
    int l = 1, r = N / inside + 1;
    // cout << diff << "\n";
    while (l < r) {
      int mid = (l + r + (r - l > 5) + 1) / 2;
      
      while (press_button() > mid) {
          vis[took.back()] = 0;
          move_outside(took.back());
          took.pop_back();
      }
      int prv = 0;
      calc(mid);
      for (auto i : vis) prv += i;
      // cerr << mid << " = " << prv << " + " << took.size() << " , total = " << diff * mid << "\n";
      if (prv == diff * mid) {
          l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
}

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