제출 #1368444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368444		avighna	드문 곤충 (IOI22_insects)	C++20	99.89 / 100	13 ms	464 KiB

insects

#include <bits/stdc++.h>

void move_inside(int i);
void move_outside(int i);
int press_button();

using namespace std;

int min_cardinality(int N) {
  mt19937 gen(random_device{}());
  vector<int> p(N);
  iota(p.begin(), p.end(), 0);
  shuffle(p.begin(), p.end(), gen);
  auto Move_inside = [&](int i) {
    move_inside(p[i]);
  };
  auto Move_outside = [&](int i) {
    move_outside(p[i]);
  };

  vector<int> used(N);
  for (int i = 0; i < N; ++i) {
    Move_inside(i);
    used[i] = 1;
    if (press_button() > 1) {
      Move_outside(i);
      used[i] = 0;
    }
  }
  int num_elems = accumulate(used.begin(), used.end(), 0);
  if (num_elems == 1) {
    return N;
  }
  if (num_elems == N) {
    return 1;
  }

  int n = N;
  vector<int> idxs(n);
  iota(idxs.begin(), idxs.end(), 0);

  int lo = 1, hi = n / num_elems;
  while (lo < hi) {
    int mi = (lo + hi + 1) / 2;
    vector<int> stk;
    for (int i = 0; i < n; ++i) {
      if (used[idxs[i]]) {
        continue;
      }
      stk.push_back(idxs[i]);
      Move_inside(idxs[i]);
      if (press_button() > mi) {
        Move_outside(idxs[i]);
        stk.pop_back();
      }
    }
    if (accumulate(used.begin(), used.end(), 0) + int(stk.size()) == mi * num_elems) {
      lo = mi;
      for (int &i : stk) {
        used[i] = 1;
      }
    } else {
      hi = mi - 1;
      for (int &i : stk) {
        Move_outside(i);
      }
      idxs = stk;
      for (int i = 0; i < N; ++i) {
        if (used[i]) {
          idxs.push_back(i);
        }
      }
      n = idxs.size();
      hi = min(hi, n / num_elems);
    }
  }
  return lo;
}

#ifdef MACOS_LOCAL
#include "stub.cpp"
#endif

• 서브태스크 1: 10 / 10
• 서브태스크 2: 15 / 15
• 서브태스크 3: 74.89 / 75