Submission #713250

#	Time	Username	Problem	Language	Result	Execution time	Memory
713250		KoD	Rarest Insects (IOI22_insects)	C++17	100 / 100	67 ms	456 KiB

insects

#include "insects.h"

#include <vector>
#include <random>

int min_cardinality(int N) {
  int kinds = 0;
  std::vector<int> type(N);
  for (int i = 0; i < N; ++i) {
    move_inside(i);
    if (press_button() > 1) {
      move_outside(i);
    } else {
      kinds += 1;
      type[i] = 1;
    }
  }
  auto check = [&](int thres) {
    int cnt = 0;
    std::vector<int> in, out;
    for (int i = 0; i < N; ++i) {
      if (type[i] == 1) {
        cnt += 1;
      } else if (type[i] == 0) {
        move_inside(i);
        if (press_button() > thres) {
          move_outside(i);
          out.push_back(i);
        } else {
          in.push_back(i);
        }
      }
    }
    if (cnt + (int)in.size() == kinds * thres) {
      for (const int i : in) {
        type[i] = 1;
      }
      return true;
    } else {
      for (const int i : in) {
        move_outside(i);
      }
      for (const int i : out) {
        type[i] = -1;
      }
      return false;
    }
  };
  int ok = 1, ng = N / kinds + 1;
  std::default_random_engine gen(0xABCDEF);
  std::uniform_int_distribution flag(0, 1);
  while (ng - ok > 1) {
    int md = (ok + ng) / 2;
    if ((ok + ng) % 2 == 1 and flag(gen)) {
      md += 1;
    }
    (check(md) ? ok : ng) = md;
  }
  return ok;
}

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