Submission #1266568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266568		scalifrastico_098	Rarest Insects (IOI22_insects)	C++20	51.52 / 100	51 ms	420 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int m, op=0, c=0, pk=0; vector<bool> fg; vector<int> uh;
bool f1(int n)
{
  if(uh.empty()) return (c==op*m); long long ne=1LL*op*m-c;if(ne>(long long)uh.size()) return false;
  vector<int> ind; vector<char> ag(fg.size(), 0); int i=pk, lk=0, s=uh.size(); long long ne1=ne; 
  while(lk<s&&ne1>0)
  {
    move_inside(uh[i]);
    if(press_button()>m){move_outside(uh[i]);}else {fg[uh[i]]=true; c++; ind.push_back(uh[i]); ne1--; ag[uh[i]]=1;}
    i++; if(i==s) i=0; lk++; long long er=s-lk;
    if(ne1>0&&er<ne1) break;
  } 
  if(ne1==0)
  {
    if(!ind.empty()){uh.erase(remove_if(uh.begin(), uh.end(), [&](int x){ return ag[x]; }), uh.end());}
    if(uh.empty()) pk=0;  else pk=i%uh.size(); return true;
  }
  for(auto x:ind){move_outside(x); fg[x]=false; c--;} 
  if(uh.empty()) pk=0; else pk=i%uh.size();
  return false;
} 
int min_cardinality(int n) { 
  op=0; c=0; pk=0; fg.assign(n, false); for(int i=0; i<n; i++){move_inside(i); if(press_button()>1) move_outside(i); else {fg[i]=true; c++; op++;}}
  for(int i=0; i<n; i++) {if(!fg[i]) uh.push_back(i);} if(op<=1) return n; if(op==n) return 1; 
  int r = n / op, l  = 1,st = 1; 
  while (l + st <= r) st <<= 1; st >>= 1;
  while (st > 0) 
  {
    if(l+st>r){st>>=1; continue; }m = l + st;if (f1(n)) l = m; st >>= 1;             
  }
  return l;
}

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