제출 #1266597

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

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int op=0, c=0, pk=0;  
int min_cardinality(int n) {
  vector<int> ind, rm; ind.reserve(n); rm.reserve(n);
  int lk=0, pl=-1; 
  for(int i=0; i<n; i++)
  {
    move_inside(i); 
    if(press_button()>1){move_outside(i); rm.push_back(i);} else ind.push_back(i); 
  }
  int k=ind.size(); if(k==0) return 0; 
  int l=1, r=n/k;
  while (l<r) 
  {
    int m=(l+r+1)/2; long long ne=1LL*k*(m-l); vector<int> y, h; y.reserve((size_t)min<long long>(ne, rm.size())); h.reserve(rm.size()); 
    if(ne>(long long)rm.size()){r=m-1; continue;}
    for(int x: rm)
    {
      if(y.size()==ne) break; move_inside(x); if(press_button()>m){move_outside(x); h.push_back(x);}
      else{y.push_back(x);}
    }
    if(y.size()==ne)
    {
      vector<char> mx(n, 0); for(auto x:y) mx[x]=1; vector<int>np; np.reserve(rm.size()-y.size());
      for(auto x:rm) if(!mx[x]) np.push_back(x); rm.swap(np); l=m;
    }
    else
    {
      for(auto x: y) move_outside(x); vector<char>mx(n, 0); for(auto x: h)mx[x]=1; vector<int>np; np.reserve(rm.size()-h.size());
      for(auto x:rm) if(!mx[x]) np.push_back(x); rm.swap(np); r=m-1;
    }            
  }
  return l;
}

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