Submission #830920

#	Time	Username	Problem	Language	Result	Execution time	Memory
830920		erray	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	55 ms	280 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/eagle/ioi22/d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

int min_cardinality(int N) {
  vector<bool> in_set(N);
  vector<bool> deact(N);
  int cur = 0;
  auto Move = [&](int x) {
    if (x < cur) {
      for (int i = 0; i < N; ++i) {
        if (in_set[i] && !deact[i]) {
          in_set[i] = false;
          move_outside(i);
        }
      }
    } 
    for (int i = 0; i < N; ++i) {
      if (!in_set[i] && !deact[i]) {
        move_inside(i);
        in_set[i] = true;
        if (press_button() > x) {
          move_outside(i);
          in_set[i] = false;
        }
      }
    }
    cur = x;
    return accumulate(in_set.begin(), in_set.end(), 0);
  };
  int K = Move(1);
  debug(K);
  int low = 2, high = (N / K) + 1;
  while (low < high) {
    int size = N - accumulate(deact.begin(), deact.end(), 0);
    int mid = low;
    int ls = K, rs = size - K;
    while (ls + K <= rs - K && mid + 1 <= high) {
      ls += K, rs -= K;
      ++mid;
    }
    if (ls > rs && mid > low) {
      --mid;
    }
    int card = Move(mid);
    debug(mid, card);
    if (card == K * mid) {
      low = mid + 1;
      for (int i = 0; i < N; ++i) {
        if (in_set[i]) {
          deact[i] = true;
        }
      }
    } else {
      for (int i = 0; i < N; ++i) {
        if (!in_set[i]) {
          deact[i] = true;
        }
      }
      high = mid;
    }
  }
  return low - 1;
}

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