Submission #1266582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266582		scalifrastico_098	Rarest Insects (IOI22_insects)	C++20	0 / 100	0 ms	408 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int m, op=0, c=0, pk=0; 
bool f1(int n)
{
  for(int i=0; i<n; i++){move_outside(i);} int lk=0, pl=-1; vector<char>ind(n, 0);
  for(int i=0; i<m; i++)
  {
    if(press_button()!=0){for(int j=0; j<n; j++) move_outside(j);}
    int uj=press_button(), ok=0; vector<int> y1; y1.reserve(n);
    for(int j=0; j<n; j++)
    {
      if(ind[j]) continue; move_inside(j); int no=press_button(); 
      if(no==uj)move_outside(j); else{uj=no; ind[j]=1; lk++; ok++; y1.push_back(j);if(lk==n) return true;}
    }
    if(i==0)
    {
      pl=ok; if(pl==0) return (n==0); 
      if(1LL*m*pl<n)
      {
        for(auto x:y1) move_outside(x); if(press_button()!=0){for(int j=0; j<n; j++) move_outside(j);}
        return false;
      }
    }
    for(auto x:y1) move_outside(x); if(press_button()!=0){for(int j=0; j<n; j++) move_outside(j);}
    if(ok==0) break; 
  }
  return (lk==n);
} 
int min_cardinality(int n) { 
  int l=1, r=n, q=n;
  while (l<=r) 
  {
    m = (l+r)/2;if (f1(n)){ r=m-1;q=m;} else l=m+1;            
  }
  return q;
}

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