제출 #1356470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356470		whally	드문 곤충 (IOI22_insects)	C++20	99.91 / 100	11 ms	440 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int n,t;

int min_cardinality(int N)
{
  vector<int> col;
  n = N;
  for (int i = 0; i < n; i++){
    t++;
    move_inside(i);
    int res = press_button();
    if (res > 1){
      move_outside(i);
      col.push_back(i);
      t--;
    }
  }
  if (t == n) return 1;
  if (t == 1) return n;

  int l = 1, r = n/t;
  int pre = t;
  int ans = -1;
  while (l <= r){
    int mid = (l+r+1)/2;

    int cnt = pre;
    vector<int> ye, no;
    //reverse(col.begin(), col.end());
    int idx = 0;
    for (int x : col){
      cnt++;
      move_inside(x);
      ye.push_back(x);
      int res = press_button();
      if (res > mid){
        cnt--;
        ye.pop_back();
        no.push_back(x);
        move_outside(x);
      }
      idx++;
      if (cnt == mid*t) break;
    }
    while (idx < (int)col.size()){
      no.push_back(col[idx]);
      idx++;
    }
    
    col.clear();
    if (cnt == mid*t){
      pre = cnt;
      for (int x : no) col.push_back(x);
      ans = mid;
      l = mid+1;
    }
    else{
      for (int x : ye){
        move_outside(x);
        col.push_back(x);
      }
      r = mid-1;
    }
  }
  if (ans == -1) ans = l;

  return ans;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 15 / 15
• 서브태스크 3: 74.91 / 75