oj.uz

Submission #858748

# Submission time Handle Problem Language Result Execution time Memory
858748 2023-10-09T06:00:04 Z NatdanaiHS Rarest Insects (IOI22_insects) C++17
0 / 100
 0 ms 344 KB 
  #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);
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Wrong answer.
3 Halted 0 ms 0 KB -