oj.uz

Submission #830553

# Submission time Handle Problem Language Result Execution time Memory
830553 2023-08-19T07:59:35 Z erray Rarest Insects (IOI22_insects) C++17
0 / 100
 1 ms 208 KB 
#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/eagle/ioi22/d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

int min_cardinality(int N) {
  vector<bool> in_set(N);
  vector<bool> deact(N);
  int cur = 0;
  auto Move = [&](int x) {
    if (x < cur) {
      cur = 0;
      for (int i = 0; i < N; ++i) {
        if (in_set[i]) {
          in_set[i] = false;
          move_outside(i);
        }
      }
    } 
    for (int i = 0; i < N; ++i) {
      if (!in_set[i] && !deact[i]) {
        move_inside(i);
        in_set[i] = true;
        if (press_button() > x) {
          move_outside(i);
          in_set[i] = false;
        }
      }
    }
    return accumulate(in_set.begin(), in_set.end(), 0);
  };
  int K = Move(1);
  debug(K);
  int low = 1, high = (N / K) + 1;
  while (low < high) {
    int mid = (low + high) >> 1; //optimize splitting point if it doesn't get 100
    int card = Move(mid);
    debug(mid, card);
    if (card == K * mid) {
      low = mid + 1;
    } else {
      for (int i = 0; i < N; ++i) {
        if (!in_set[i]) {
          deact[i] = true;
        }
      }
      high = mid;
    }
  }
  return low - 1;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 75.0

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