제출 #858743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858743		NatdanaiHS	드문 곤충 (IOI22_insects)	C++17	25 / 100	208 ms	596 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)&&false){
      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++){
        int now=0;
        for(int j=0;j<N;j++){
          if(flag[i])continue;
          flag[i]=true;
          move_inside(i);
          if(press_button()>now)now++;
          else{
            move_outside(i);
            flag[i]=false;
          }
        }
        ans=min(ans,now);
      }
    }
    else while(updatemin(ans+1,N)&&ans<=2000)ans++;

    return ans;
  }

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