제출 #830571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830571		erray	드문 곤충 (IOI22_insects)	C++17	83.56 / 100	91 ms	284 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]) {
          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 = 1, high = (N / K) + 1;
  while (low < high) {
    int mid = (low + high) >> 1; //optimize splitting point if it doesn't get 100
    int card = Move(mid);
    debug(mid, card);
    if (card == K * mid) {
      low = mid + 1;
    } 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: 58.56 / 75