Submission #1124194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124194		epicci23	Rarest Insects (IOI22_insects)	C++17	0 / 100	3 ms	408 KiB

insects

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

vector<int> v,Left;
int D;

void Clear(){
  while(!v.empty()){
    move_outside(v.back());
    v.pop_back();
  }
}

int min_cardinality(int n){
  for(int i=0;i<n;i++){
    v.push_back(i);
    move_inside(i);
    int u = press_button();
    if(u == 1) continue;
    move_outside(i);
    v.pop_back();
  }

  D = v.size();
  for(int i=0;i<n;i++) Left.push_back(i);

  if(D > n / 2) return 1;
  if(D == 1) return n;
  
  int l = 1 , r = n / D;
  while(l < r){
    int B = (l + r + 1) / 2;
    Clear();
    for(int i=0;i<Left.size();i++){
      v.push_back(Left[i]);
      move_inside(Left[i]);
      int u = press_button();
      if(u > B){
        move_outside(Left[i]);
        v.pop_back();
      }
    }
    if(v.size() == B * D) l = B;
    else r = B - 1;
    Left = v;
  }

  return l;
}

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