Submission #1266614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266614		scalifrastico_098	Rarest Insects (IOI22_insects)	C++20	99.95 / 100	15 ms	472 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;
  while (l<r) 
  {
    r = min(r, l + (int)(rm.size() / k));
    int m=(l+r+1)/2; long long ne=1LL*k*(m-l); 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: 74.95 / 75