Submission #1045643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045643		Soumya1	Rarest Insects (IOI22_insects)	C++17	99.78 / 100	34 ms	944 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int get_distinct(int n) {
  vector<int> ans = {0};
  move_inside(0);
  for (int i = 1; i < n; i++) {
    move_inside(i);
    if (press_button() != 1) {
      move_outside(i);
    } else {
      ans.push_back(i);
    }
  }
  for (int i : ans) move_outside(i);
  return ans.size();
}
int min_cardinality(int n) {
  int d = get_distinct(n);
  int lo = 1, hi = n / d;
  vector<int> all(n);
  iota(all.begin(), all.end(), 0);
  int total_in = 0;
  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:35:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     if (total_in + in.size() == d * mid) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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