Submission #627238

#	Time	Username	Problem	Language	Result	Execution time	Memory
627238		model_code	Rarest Insects (IOI22_insects)	C++17	100 / 100	689 ms	2516 KiB

insects

// correct/solution-prabowo-ac.cpp
#include "insects.h"

#include <map>
#include <numeric>
#include <vector>

int N;
std::vector<bool> lastPress, where;

void _move_inside(int i) {
  where[i] = true;
}

void _move_outside(int i) {
  where[i] = false;
}

std::map<std::vector<bool>, int> memo;
int _press_button() {
  if (memo.find(where) != memo.end()) return memo[where];
  for (int i = 0; i < N; ++i) {
    if (where[i] == lastPress[i]) continue;
    if (where[i]) move_inside(i);
    else move_outside(i);
  }
  lastPress = where;
  return memo[where] = press_button();
}

int min_cardinality(int _N) {
  N = _N;
  lastPress.assign(N, false); where.assign(N, false);

  std::vector<int> insects(N);
  std::iota(insects.begin(), insects.end(), 0);

  std::vector<bool> isInside(N);

  // Count distincts
  std::vector<int> insides, outsides;
  int inside = 0;
  for (int insect : insects) {
    _move_inside(insect);
    if (_press_button() > 1) {
      _move_outside(insect);
      outsides.push_back(insect);
    } else {
      insides.push_back(insect);
      ++inside;
    }
  }
  int distinct = inside;
  insects = outsides;

  int l = 1, r = N / distinct;
  int ans = -1;
  while (l <= r) {
    int mid = (l + r + 1) / 2;

    insides.clear(); outsides.clear();
    for (int insect : insects) {
      _move_inside(insect);
      if (_press_button() > mid) {
        _move_outside(insect);
        outsides.push_back(insect);
      } else {
        insides.push_back(insect);
        ++inside;
      }
    }

    if (inside == mid * distinct) {
      ans = mid;
      l = mid + 1;
      insects = outsides;
    } else {
      r = mid - 1;
      insects = insides;
      for (int insect : insects) {
        _move_outside(insect);
        --inside;
      }
    }
  }

  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75