oj.uz

Submission #859319

# Submission time Handle Problem Language Result Execution time Memory
859319 2023-10-10T03:58:25 Z NatdanaiHS Rarest Insects (IOI22_insects) C++17
0 / 100
 32 ms 592 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;
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
  int l=1,r=N/snow;
  while(l<=r){
    int mid=(l+r)/2;
    stack<int> rollback;
    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,rollback.push(i);
        else{
            cnt++;
            rollback.push(i);
        }
    }
    if(cnt==(mid-ans)*snow){
        ans=mid;
        l=mid+1;
        while(rollback.size()){
            flag[rollback.top()]=!flag[rollback.top()];
            rollback.pop();
        }
    }
    else{
        r=mid-1;
        // while(rollback.size()){
        //     move_outside(rollback.top());
        //     rollback.pop();
        // }
    }
  }
  return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 416 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Incorrect 3 ms 344 KB Wrong answer.
13 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 416 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Incorrect 3 ms 344 KB Wrong answer.
13 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 22 ms 592 KB Output is correct
8 Correct 9 ms 344 KB Output is correct
9 Correct 22 ms 416 KB Output is correct
10 Correct 24 ms 416 KB Output is correct
11 Correct 32 ms 412 KB Output is correct
12 Correct 14 ms 428 KB Output is correct
13 Incorrect 28 ms 420 KB Wrong answer.
14 Halted 0 ms 0 KB -