Submission #652779

#	Time	Username	Problem	Language	Result	Execution time	Memory
652779		Blagoj	Rarest Insects (IOI22_insects)	C++17	100 / 100	70 ms	312 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
 
using namespace std;
 
bool good[2001];
 
int Unique(int N)
{
  int cnt = 0;
  for (int i = 0; i < N; i++)
  {
    move_inside(i);
    if (press_button() == 2)
    {
      move_outside(i);
      continue;
    }
    good[i] = false;
    cnt++;
  }
  return cnt;
}

mt19937 _rand(time(NULL));

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

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