제출 #1368300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368300		avighna	드문 곤충 (IOI22_insects)	C++20	50 / 100	40 ms	436 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) {
  // if we limit the acceptor to 1, we're gonna get the first occurence of each element
  // this lets us count the number of elements

  // then, if we pass again and limit the acceptor to 2, we get the first and second occurences
  // of each element

  // eventually, we'll get to a point where x occurences will not have x * <num in first>
  // this is when an element only has < x occurences

  vector<int> firsts;
  for (int i = 0; i < N; ++i) {
    move_inside(i);
    firsts.push_back(i);
    if (press_button() == 2) {
      move_outside(i);
      firsts.pop_back();
    }
  }
  int num_elems = firsts.size();
  for (int &i : firsts) {
    move_outside(i);
  }

  if (num_elems == 1) {
    return N;
  }
  if (num_elems == N) {
    return 1;
  }

  int x = *ranges::partition_point(views::iota(1, N / num_elems + 1), [&](int x) {
    vector<int> v;
    for (int i = 0; i < N; ++i) {
      move_inside(i);
      v.push_back(i);
      if (press_button() > x) {
        move_outside(i);
        v.pop_back();
      }
    }
    for (int &i : v) {
      move_outside(i);
    }
    return int(v.size()) == x * num_elems;
  });
  return x - 1;
}

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

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