Submission #1266591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266591		scalifrastico_098	Rarest Insects (IOI22_insects)	C++20	96.29 / 100	15 ms	424 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int m, op=0, c=0, pk=0;  
int min_cardinality(int n) {
  for(int i=0; i<n; i++){move_outside(i);} 
  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) 
  {
    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()); 
    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: 71.29 / 75