Submission #838740

#	Time	Username	Problem	Language	Result	Execution time	Memory
838740		taher	Rarest Insects (IOI22_insects)	C++17	95.34 / 100	54 ms	424 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;
  };
  
  int base = (int) roots.size();
  vector<int> possible;
  for (int i = 0; i < n; i++) {
    possible.push_back(i); 
  }
 
  auto Check = [&](int mid) {
    vector<int> tmp;
    for (int id = 0; id < (int) possible.size(); id++) {
      int i = possible[id];
      if (in[i]) {
        continue; 
      }
      move_inside(i);
      if (press_button() > mid) {
        move_outside(i);
      } else {
        tmp.push_back(i);
        roots.push_back(i);
        in[i] = true;
      } 
    }
    if ((int) roots.size() == base * mid) {
      return true;
    }
    possible = roots;
    for (int i = 0; i < (int) tmp.size(); i++) {
      roots.pop_back(); 
      in[tmp[i]] = false;
      move_outside(tmp[i]);
    }
    return false;
  };
  
  int low = max(2, get_low_bound());
  int high = 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: 70.34 / 75