Submission #1196118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196118		hyakup	Rarest Insects (IOI22_insects)	C++20	99.89 / 100	15 ms	424 KiB

insects

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

int min_cardinality( int n ){
  vector<int> marc(n);
  int k = 0;
  for( int i = 0; i < n; i++ ){
    move_inside(i);
    if( press_button() > 1 ) move_outside(i);
    else{
      marc[i] = 2;
      k++;
    }
  }

  int inside = k;

  auto check = [&]( int val ){
    for( int i = 0; i < n; i++ ) if( marc[i] != -1 && marc[i] != 2 ){
      move_inside(i);
      if( press_button() > val ) move_outside(i);
      else marc[i] = 1, inside++;
    }

    return (inside == val*k);
  };

  int l = 1, r = n/k;
  while( l < r ){
    int mid = ( l + r + 1 )/2;
    if( check(mid) ){
      for( int i = 0; i < n; i++ ) if( marc[i] == 1 ) marc[i] = 2;
      l = mid;
    }
    else{
      for( int i = 0; i < n; i++ ){
        if( marc[i] == 1 ) move_outside(i), marc[i] = 0, inside--;
        else if( marc[i] == 0 ) marc[i] = -1;
      }
      r = mid - 1;
    }
  }

  return l;
}

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