Submission #859029

#	Time	Username	Problem	Language	Result	Execution time	Memory
859029		NatdanaiHS	Rarest Insects (IOI22_insects)	C++17	25 / 100	184 ms	920 KiB

insects

  #include "insects.h"
  #include <bits/stdc++.h>
  using namespace std;
  //move_inside
  //move_outside
  //press_button
  vector<bool> flag(2020,false);
  int ans=1,snow=1;
  bool updatemin(int need,int N){
    int cnt=0;
    for(int i=0;i<N;i++){
      if(cnt==snow)return true;
      if(flag[i])continue;
      cnt++;
      move_inside(i);
      flag[i]=true;
      if(press_button()==need)continue;
      else{
        move_outside(i);
        flag[i]=false,cnt--;

      }
    }
    return cnt==snow;
  }
  int min_cardinality(int N) {
    flag[0]=true;
    move_inside(0);
    //Prime Set
    for(int i=1;i<N;i++){
      move_inside(i);
      if(press_button()!=1)move_outside(i);
      else snow++,flag[i]=true;
    }
    //find ans
    if(snow<=sqrt(N)){
      for(int i=0;i<N;i++){
        if(flag[i]){
          flag[i]=false;
          move_outside(i);
        }
      }
      ans=N;
      
      for(int i=0;i<N;i++){
        if(flag[i])continue;
        stack<int> C;
        int now=1;
        C.push(i);
        move_inside(i);
        for(int j=i+1;j<N;j++){
          if(flag[j])continue;
          move_inside(j);
          C.push(j);
          if(press_button()>now)now++;
          else{
            move_outside(j);
            C.pop();
          }
        }
        ans=min(ans,now);
        while(C.size()){
          flag[C.top()]=true;
        	move_outside(C.top());
          C.pop();
        }
      }
    }
    else while(updatemin(ans+1,N)&&ans<=2000)ans++;

    return ans;
  }

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