Submission #1070408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070408		noyancanturk	Rarest Insects (IOI22_insects)	C++17	54.05 / 100	129 ms	596 KiB

insects

#include "insects.h"

#include<iostream>

int min_cardinality(int n) {
  int types[n]{};
  bool arein[n]{};
  int last=0;
  auto push=[&](int i){
    move_inside(i);
    arein[i]=1;
  };
  auto pop=[&](int i){
    move_outside(i);
    arein[i]=0;
  };
  auto query=[&](){
    return last=press_button();
  };
  types[0]=1;
  push(0);
  int headcnt=1;
  for(int i=1;i<n;i++){
    push(i);
    int cnt=query();
    if(cnt!=1){
      types[i]=2;
      pop(i);
    }else headcnt+=types[i]=1;
  }
  int ans=1;
  int cnt=headcnt;
  int l=2,r=n/headcnt;
  while(l<=r){
    int mid=l+r>>1;
    for(int i=0;i<n;i++){
      if(mid<types[i]&&arein[i]&&mid<last){
        pop(i),cnt--;
      }
    }
    for(int i=0;i<n;i++){
      if(arein[i])continue;
      push(i),cnt++;
      int cnt1=query();
      if(mid<cnt1)pop(i),cnt--;
      if(types[i]<cnt1)types[i]=cnt1;
    }
    if(cnt==headcnt*mid){
      ans=mid;
      l=mid+1;
    }else{
      r=mid-1;
    }
  }
  return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid=l+r>>1;
      |             ~^~

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