제출 #1368447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368447		avighna	드문 곤충 (IOI22_insects)	C++20	99.95 / 100	11 ms	448 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) {
  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);

  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, cnt = accumulate(used.begin(), used.end(), 0); i < n; ++i) {
      if (used[idxs[i]] || cnt + int(stk.size()) == mi * num_elems) {
        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;
}

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