제출 #713249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713249		KoD	드문 곤충 (IOI22_insects)	C++17	99.89 / 100	65 ms	412 KiB

insects

#include "insects.h"

#include <vector>

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;
  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: 74.89 / 75