Submission #1045662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045662		Soumya1	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	36 ms	696 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
  vector<int> all;
  int d = 1;
  move_inside(0);
  for (int i = 1; i < n; i++) {
    move_inside(i);
    if (press_button() != 1) {
      move_outside(i);
      all.push_back(i);
    } else {
      d++;
    }
  }
  int lo = 1, hi = n / d;
  int total_in = d;
  auto check = [&](int mid) {
    vector<int> in, out;
    for (int i : all) {
      move_inside(i);
      if (press_button() > mid) {
        out.push_back(i);
        move_outside(i);
      } else {
        in.push_back(i);
      }
    }
    if (total_in + in.size() == d * mid) {
      total_in += in.size();
      all = out;
      return true;
    }
    for (int i : in) move_outside(i);
    all = in;
    return false;
  };
  while (lo < hi) {
    int mid = (lo + hi + 1) >> 1;
    if (check(mid)) lo = mid;
    else hi = mid - 1;
  }
  return lo;
}

Compilation message (stderr)

insects.cpp: In lambda function:
insects.cpp:30:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |     if (total_in + in.size() == d * mid) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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