Submission #627660

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

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;

const int maxn = 2010;
bool in[maxn];

pair<bool, int> p(int x, int N) {
  for (int i = 0; i < N; ++i) {
    move_inside(i);
    in[i] = 1;
    if (press_button() > x) {
      move_outside(i);
      in[i] = 0;
    }
  }

  for (int i = 0; i < N; ++i) {
    if (in[i]) {
      move_outside(i);
    }
  }

  int cnt = 0, bad = 0;
  for (int i = 0; i < N; ++i) {
    if (in[i]) {
      move_inside(i);
      if (press_button() >= x) {
        move_outside(i);
        bad += 1;
      }
      cnt += 1;
      in[i] = 0;
    }
  }

  return {cnt == bad * (x - 1), bad};
}

int min_cardinality(int N) {

  pair<bool, int> temp;
  int lo = 1, hi = min(N, 1000);
  while (lo < hi) {
    int mid = (lo + hi + 1) / 2;
    if ((temp = p(mid, N)).first) lo = mid;
    else hi = mid-1;
  }

  if (lo == 1000 && temp.second == 1) return N;
  return lo;
}

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