Submission #1234124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234124		trimkus	Rarest Insects (IOI22_insects)	C++20	83.60 / 100	29 ms	460 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<int> vis(N);
    int inside = 0;
    int diff = 0;
    vector<int> took;
    vector<int> move_out;
    auto calc = [&](int till, bool first = false) -> void {
      for (int i : ord) {
        if (vis[i] != 0) continue;
          move_inside(i);
          if (press_button() > till) {
            move_outside(i);
            move_out.push_back(i);
          } else {
            took.push_back(i);
            inside += 1;
            vis[i] = 1;
            if (first) diff += 1;
          }
      }
    };
    calc(1, true);
    bool rem = false;
    int l = 1, r = N / inside + 1;
    // cout << diff << "\n";
    while (l < r) {
      int mid = (l + r + 1 + (r - l > 5)) / 2;
      
      move_out.clear();
      int prv = 0;
      calc(mid);
      for (auto i : vis) {
        if (i > 0) prv += 1;
      }
      // cerr << mid << " " << prv << " " << diff << "\n";
      // cerr << mid << " = " << prv << " + " << took.size() << " , total = " << diff * mid << "\n";
      if (prv == diff * mid) {
          l = mid;
          rem = false;
      } else {
        rem = true;
        while (took.size()) {
            vis[took.back()] = 0;
            move_outside(took.back());
            took.pop_back();
        }
        while (move_out.size()) {
          vis[move_out.back()] = -1;
          move_out.pop_back();
        }
        r = mid - 1;
      }
    }
    return l;
}

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