Submission #838750

#	Time	Username	Problem	Language	Result	Execution time	Memory
838750		taher	드문 곤충 (IOI22_insects)	C++17	99.89 / 100	51 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; 
  }
  
  int base = (int) roots.size();
  vector<int> possible;
  for (int i = 0; i < n; i++) {
    possible.push_back(i); 
  }
  
  vector<int> max_value(n);
  vector<int> min_value(n, 1234567);
 
  auto Check = [&](int mid) {
    vector<int> tmp;
    for (int id = 0; id < (int) possible.size(); id++) {
      int i = possible[id];
      if (in[i] || max_value[i] > mid) {
        continue; 
      }
      move_inside(i);
      
      if (min_value[i] < mid) {
        tmp.push_back(i);
        roots.push_back(i);
        in[i] = true; 
      } else {
        if (press_button() > mid) {
          max_value[i] = max(max_value[i], mid);
          move_outside(i);
        } else {
          min_value[i] = min(min_value[i], mid);
          tmp.push_back(i);
          roots.push_back(i);
          in[i] = true;
        }
      }
    }
    if ((int) roots.size() == base * mid) {
      sort(roots.begin(), roots.end());
      return true;
    }
    possible = roots;
    for (int i = 0; i < (int) tmp.size(); i++) {
      roots.pop_back(); 
      in[tmp[i]] = false;
      move_outside(tmp[i]);
    }
    sort(roots.begin(), roots.end());
    sort(possible.begin(), possible.end());
    return false;
  };
  
  int low = 2;
  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: 74.89 / 75