Submission #652601

#	Time	Username	Problem	Language	Result	Execution time	Memory
652601		Blagoj	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	208 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

int min_cardinality(int N) {
  // move_inside(int i);
  // void move_outside(int i);
  // press_button();
  int l = 1, r = N + 1, mid;
  vector<int> used;
  queue<int> q;
  for (int i = 0; i < N; i++)
  {
    q.push(i);
  }
  while (l + 1 < r)
  {
    mid = (l + r) / 2;
    if (used.size() > 0)
    {
      for (auto x : used)
      {
        move_outside(x);
      }
      used = {};
    }
    int k = q.size();
    queue<int> to_remove;
    while (k--)
    {
      int y = q.front();
      q.pop();
      move_inside(y);
      if (press_button() > mid)
      {
        to_remove.push(y);
        continue;
      }
      used.push_back(y);
      q.push(y);
    }
    if (used.size() % mid == 0)
    {
      while (!to_remove.empty())
      {
        used.push_back(to_remove.front());
        q.push(to_remove.front());
        to_remove.pop();
      }
      l = mid;
    }
    else
    {
      while (!to_remove.empty())
      {
        move_outside(to_remove.front());
        to_remove.pop();
      }
      r = mid;
    }
  }
  return l;
}

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