Submission #1070501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070501		noyancanturk	Rarest Insects (IOI22_insects)	C++17	99.95 / 100	44 ms	344 KiB

insects

#include "insects.h"

#include<iostream>

int min_cardinality(int n) {
  int types[n]{},cert[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=[&](){
    last=press_button();
  };
  types[0]=cert[0]=1;
  push(0);
  int headcnt=1;
  for(int i=1;i<n;i++){
    push(i);
    query();
    if(last!=1){
      types[i]=cert[i]=2;
      pop(i);
    }else headcnt+=types[i]=cert[i]=1;
  }
  last=1;
  int ans=1;
  int cnt=headcnt;
  int l=2,r=n/headcnt;
  int opcnt1=0,opcnt2=0;
  while(l<=r){
    int mid=l+r>>1;
    int past=last;
    for(int i=0;i<n;i++){
      if(mid<cert[i]&&arein[i]&&mid<last){
        pop(i),cnt--,past--;
        if(past<=mid)query(),past=last,opcnt1++;
      }
    }
    for(int i=0;i<n;i++){
      if(mid<types[i]&&arein[i]&&mid<last){
        pop(i),cnt--,past--;
        if(past<=mid)query(),past=last,opcnt1++;
      }
    }
    for(int i=0;i<n&&cnt<headcnt*mid;i++){
      if(arein[i]||mid<types[i])continue;
      int llast=last;
      push(i),cnt++;
      query();
      opcnt2++;
      if(llast!=last)cert[i]=std::max(cert[i],last);
      types[i]=std::max(types[i],last);
      if(mid<last)pop(i),cnt--,last--;
    }
    for(int i=0;i<n&&cnt<headcnt*mid;i++){
      if(arein[i]||mid<cert[i])continue;
      int llast=last;
      push(i),cnt++;
      query();
      opcnt2++;
      if(llast!=last)cert[i]=std::max(cert[i],last);
      types[i]=std::max(types[i],last);
      if(mid<last)pop(i),cnt--,last--;
    }
    if(cnt==headcnt*mid){
      ans=mid;
      l=mid+1;
    }else{
      r=cnt/headcnt;
    }
  }
  return ans;
}

Compilation message (stderr)

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

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