제출 #1233967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233967		trimkus	드문 곤충 (IOI22_insects)	C++20	53.16 / 100	49 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 + 1) / 2;
      took.clear();
      int prv = l * diff;
      calc(mid);
      // cerr << mid << " = " << prv << " + " << took.size() << " , total = " << diff * mid << "\n";
      if (prv + (int)took.size() == diff * mid) {
          l = mid;
      } else {
        while (took.size()) {
          move_outside(took.back());
          vis[took.back()] = 0;
          took.pop_back();
        }
        r = mid - 1;
      }
    }
    return l;
}

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