Submission #838700

#	Time	Username	Problem	Language	Result	Execution time	Memory
838700		taher	Rarest Insects (IOI22_insects)	C++17	25 / 100	109 ms	420 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

int min_cardinality(int N) {
  int n = N;
  vector<int> in(n);
  
  vector<int> roots;
  for (int i = 0; i < n; i++) {
    move_inside(i);
    if (press_button() == 2) {
      move_outside(i); 
    } else {
      roots.push_back(i);
      in[i] = true; 
    }
  }
  assert((int) roots.size() > 0);
  
  if ((int) roots.size() == 1) {
    return n; 
  }
  
  auto get_low_bound = [&]() {
    for (int i = 0; i < n; i++) {
      if (in[i]) {
        continue; 
      }
      move_inside(i); 
    }
    int big = press_button();
    for (int i = 0; i < n; i++) {
      if (in[i]) {
        continue; 
      }
      move_outside(i); 
    }
    
    int low = 1, high = n / (int) roots.size();
    
    auto Can = [&](int mid) {
      int restant = n - mid;
      if ((restant + (int) roots.size() - 2) / ((int) roots.size() - 1) > big) {
        return false; 
      }
      return true;
    };
    
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (Can(mid)) {
        high = mid - 1;
      } else {
        low = mid + 1; 
      } 
    }
    ++high;
    return high;
  };
  
  auto Check = [&](int mid) {
    vector<int> cnt;
    for (int i = 0; i < n; i++) {
      if (in[i]) {
        continue; 
      }
      move_inside(i);
      if (press_button() > mid) {
        move_outside(i);
      } else {
        cnt.push_back(i);
      } 
    }
    for (int i = 0; i < (int) cnt.size(); i++) {
      move_outside(cnt[i]); 
    }
    if ((int) cnt.size() == (mid - 1) * (int) roots.size()) {
      return true; 
    }
    return false;
  };
  
  int low = get_low_bound();
  int high = min(low + (1 << 7), n / (int) roots.size());
  
  while (low <= high) {
    int mid = low + (high - low) / 2;
    
    if (Check(mid)) {
      low = mid + 1;
    } else  {
      high = mid - 1; 
    } 
  }
  --low;
  return low;
}

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