Submission #652606

#	Time	Username	Problem	Language	Result	Execution time	Memory
652606		Blagoj	Rarest Insects (IOI22_insects)	C++17	45.46 / 100	260 ms	560 KiB

insects

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

using namespace std;

int Unique(int N)
{
  int cnt = 0;
  queue<int> used;
  for (int i = 0; i < N; i++)
  {
    move_inside(i);
    if (press_button() == 2)
    {
      used.push(i);
      move_outside(i);
      continue;
    }
    cnt++;
  }
  while (used.size() > 0)
  {
    move_outside(used.front());
    used.pop();
  }
  return cnt;
}

bool good[2001];

int min_cardinality(int N) {
  // move_inside(int i);
  // void move_outside(int i);
  // press_button();
  for (int i = 0; i < N; i++)
  {
    good[i] = true;
  }
  int unique = Unique(N);
  int l = 1, r = N + 1, mid;
  while (l + 1 < r)
  {
    mid = (l + r) / 2;
    int area = 0;
    queue<int> bad;
    queue<int> used;
    for (int i = 0; i < N; i++)
    {
      if (good[i])
      {
        move_inside(i);
        if (press_button() > mid)
        {
          bad.push(i);
          move_outside(i);
        }
        else
        {
          used.push(i);
          area++;
        }
      }
    }
    while (!used.empty())
    {
      move_outside(used.front());
      used.pop();
    }
    if (area == unique * mid)
    {
      l = mid;
    }
    else
    {
      while (!bad.empty())
      {
        good[bad.front()] = false;
        bad.pop();
      }
      r = mid;
    }
  }
  return l;
}

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