Submission #631740

#	Time	Username	Problem	Language	Result	Execution time	Memory
631740		AmirElarbi	Rarest Insects (IOI22_insects)	C++17	45.46 / 100	240 ms	544 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define ve vector
#define vi ve<int>
#define ii pair<int,int>
#define ll long long
#define vvi ve<vi>
#define se second
#define fi first
#define pb push_back

using namespace std;
const int nax = 2e3+5;
const int MOD = 1e9+7;

int pref[nax];
int min_cardinality(int n) {
  int type  = 0;
  for (int i = 0; i < n; ++i)
  {
       move_inside(i);
       int a = press_button();
       if(a == 1)
        type++;
       else 
        move_outside(i);
      pref[i] = type;
  }
  for (int i = 0; i < n; ++i)
  {
    move_outside(i);
  }
  int l = 0,r = n+1, ans = 0;
  while(l< r){
    int md = (l+r)/2;
    int nb = 0;
    vi cur;
    for (int i = 0; i < n; ++i)
    {
      move_inside(i);
      int a = press_button();
      if(a  > md){
        move_outside(i);
      } else {
        nb++;
        cur.pb(i);
      }
    }
    if(type*md == nb){
      l = md+1; ans = md; 
    } else {
      r = md;
    }
    for (auto i : cur)
    {
      move_outside(i);
    }
  }
  return ans;
}

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