Submission #838717

#	Time	Username	Problem	Language	Result	Execution time	Memory
838717		taher	드문 곤충 (IOI22_insects)	C++17	57.28 / 100	110 ms	428 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; 
  }
  
  if ((int) roots.size() <= 5) {
    int res = 1234567;
    
    for (int i = 0; i < (int) roots.size(); i++) {
      move_outside(roots[i]); 
    }
    for (int it = 0; it < (int) roots.size(); it++) {
      move_inside(roots[it]);
      int cnt = 1;
      
      for (int j = 0; j < n; j++) {
        if (j == roots[it]) {
          continue; 
        }
        
        move_inside(j);
        if (press_button() == 2) {
          cnt++; 
        }
        move_outside(j);
      }
      
      res = min(res, cnt);
      move_outside(roots[it]); 
    }
    return res;  
  }  
  
  int base = (int) roots.size();
 
  auto Check = [&](int mid) {
    vector<int> tmp;
    for (int i = 0; i < n; i++) {
      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; 
    }
    for (int i = 0; i < (int) tmp.size(); i++) {
      roots.pop_back(); 
      in[tmp[i]] = false;
      move_outside(tmp[i]);
    }
    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: 32.28 / 75