Submission #713246

#	Time	Username	Problem	Language	Result	Execution time	Memory
713246		KoD	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	197 ms	444 KiB

insects

#include "insects.h"

#include <vector>

int min_cardinality(int N) {
  std::vector<int> in;
  for (int i = 0; i < N; ++i) {
    move_inside(i);
    if (press_button() > 1) {
      move_outside(i);
    } else {
      in.push_back(i);
    }
  }
  int kinds = (int)in.size();
  for (int i : in) {
    move_outside(i);
  }
  auto check = [&](int thres) {
    in.clear();
    for (int i = 0; i < N; ++i) {
      move_inside(i);
      if (press_button() > thres) {
        move_outside(i);
      } else {
        in.push_back(i);
      }
    }
    for (int i : in) {
      move_outside(i);
    }
    return (int)in.size() == kinds * thres;
  };
  int ok = 1, ng = N / kinds + 1;
  while (ng - ok > 1) {
    int md = (ok + ng) / 2;
    (check(md) ? ok : ng) = md;
  }
  return ok;
}

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