Submission #859468

#	Time	Username	Problem	Language	Result	Execution time	Memory
859468		NatdanaiHS	Rarest Insects (IOI22_insects)	C++17	0 / 100	0 ms	344 KiB

insects

#include "insects.h"
  #include <bits/stdc++.h>
  using namespace std;
  vector<bool> flag(2020,false);
  int ans=1,snow=1,mxans=0;
  int min_cardinality(int N) {
    for(int i=0;i<N;i++){
      move_inside(i);
      if(press_button()>1)move_outside(i);
      else snow++,flag[i]=true;
    }
    int l=1,r=N/snow+1;
    while(l<=r){
      int mid=(l+r)/2;
      stack<int> rollA,rollB;
      int cnt=0;
      for(int i=0;i<N;i++){
          if(cnt==(mid-ans)*snow)break;
          if(flag[i])continue;
          move_inside(i);
          // 
          if(press_button()>mid)move_outside(i),flag[i]=true,rollA.push(i);
          else{
              cnt++;
              rollB.push(i);
          }
      }
      if(cnt==(mid-ans)*snow){
          ans=mid;
          l=mid+1;
          while(rollA.size()){
              flag[rollA.top()]=!flag[rollA.top()];
              rollA.pop();
          }
          while(rollB.size()){
              flag[rollB.top()]=!flag[rollB.top()];
              rollB.pop();
          }
      }
      else{
          r=mid-1;
          while(rollB.size()){
              move_outside(rollB.top());
              rollB.pop();
          }
      }
    }
    return ans;
  }

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