Submission #627764

#	Time	Username	Problem	Language	Result	Execution time	Memory
627764		Fischer	Rarest Insects (IOI22_insects)	C++17	0 / 100	28 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);
      in[i] = 0;
      if (press_button() >= x) {
        move_outside(i);
        in[i] = 1;
        bad += 1;
      }
      cnt += 1;
    }
  }
  for (int i = 0; i < N; ++i) {
    if (in[i]) {
      move_outside(i);
      in[i] = 0;
    }
  }
  	
  return {cnt == bad * x, bad};
}
 
int min_cardinality(int N) {
 
  pair<bool, int> temp;
  int lo = 1, hi = N;
  while (lo < hi) {
    int mid = (lo + hi + 1) / 2;
    if ((temp = p(mid, N)).first) lo = mid;
    else hi = mid-1;
  }
 
  return lo;
}

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