제출 #1266617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266617		scalifrastico_098	드문 곤충 (IOI22_insects)	C++20	100 / 100	15 ms	520 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
  vector<int> ind; set<int> rm; ind.reserve(n); 
  int lk=0, pl=-1; move_inside(0); ind.push_back(0); 
  for(int i=1; i<n; i++)
  {
    move_inside(i); 
    if(press_button()>1){move_outside(i); rm.insert(i);} else ind.push_back(i); 
  }
  int k=ind.size(); if(k==0) return 0; 
  int l=1, r=n/k; r = min(r, l + (int)(rm.size() / k));
  while (l<r) 
  {
    int m = l + (r - l + 1 + (r - l > 5)) / 2; long long ne=1LL*k*(m-l); if(ne==0){l=m; continue;}if(ne>rm.size()){r=m-1; continue;}
    vector<int> y, h; y.reserve((size_t)min<long long>(ne, rm.size())); h.reserve(rm.size()); long long pu=0;
    for(auto it =rm.begin();it != rm.end() && y.size() < ne; it++, pu++)
    {
      long long u=rm.size()-pu, v=ne-y.size(); if(u<v) break; int x=*it; move_inside(x); if(press_button()>m){move_outside(x); h.push_back(x);}
      else y.push_back(x);
    }
    if(y.size()==ne)
    {
      for(auto x:y) rm.erase(x); l=m;
    }
    else
    {
      if(!y.empty()){for(auto x:y)move_outside(x);}
      for(auto x:h) rm.erase(x); r=m-1;
    }            
  }
  return l;
}

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