Submission #627230

#	Time	Username	Problem	Language	Result	Execution time	Memory
627230		model_code	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	115 ms	428 KiB

insects

// correct/solution-hocky-blacklist-binser.cpp
#include "insects.h"

#include <bits/stdc++.h>
using namespace std;

int min_cardinality(int N) {

  vector<int> device;
  vector<int> checking_set;

  for (int i = 0; i < N; i++) {
    move_inside(i);
    int max_occurrence = press_button();
    if (max_occurrence == 2) {
      move_outside(i);
      checking_set.push_back(i);
    } else {
      device.push_back(i);
    }
  }

  int distinct = device.size();
  auto get_bounds = [&](int device_size, int checking_size) -> pair<int, int> {
    return {device_size / distinct, (device_size + checking_size) / distinct};
  };

  vector <int> blacklist(N);
  pair<int, int> bounds = get_bounds(device.size(), checking_set.size());

  vector<pair<int, int>> just_moved;
  do {
    if (bounds.first == bounds.second) {
      return bounds.first;
    }
    assert(bounds.first < bounds.second);
    int middle = (bounds.first + bounds.second + 1) / 2;
    vector<int> next_checking_set;
    for (const auto &insect : checking_set) {
      if(blacklist[insect]) {
        next_checking_set.push_back(insect);
        continue;
      }
      move_inside(insect);
      int max_occurrence = press_button();
      if (max_occurrence > middle) {
        move_outside(insect);
        next_checking_set.push_back(insect);
      } else {
        just_moved.push_back({insect, max_occurrence});
      }
    }
    if ((int) just_moved.size() + (int) device.size() == distinct * middle) {
      // Increase the lower bound
      for (const auto &insect : just_moved) {
        device.push_back(insect.first);
      }
      swap(checking_set, next_checking_set);
      bounds = get_bounds(device.size(), checking_set.size());
      just_moved.clear();
      blacklist.assign(N, 0);
    } else {

      // Decrease the upper bound
      bounds = get_bounds(device.size(), just_moved.size());
      if (bounds.first < bounds.second) {
        checking_set.clear();
        int next_middle = (bounds.first + bounds.second + 1) / 2;
        int pushed = 0;
        for (int i = 0; i < (int) just_moved.size(); i++) {
          const auto &insect = just_moved[i];
          if (insect.second <= next_middle) {
            pushed++;
          } else {
            if(i > 0 && just_moved[i - 1].second < just_moved[i].second) blacklist[insect.first] = 1;
            move_outside(insect.first);
            checking_set.push_back(insect.first);
          }
        }
        just_moved.resize(pushed);
      } else {
        return bounds.first;
      }
    }
  } while (true);

  return 0;
}

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