oj.uz

Submission #830583

# Submission time Handle Problem Language Result Execution time Memory
830583 2023-08-19T08:11:11 Z erray Rarest Insects (IOI22_insects) C++17
0 / 100
 2000 ms 280 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) {
      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;
        }
      }
    }
    cur = x;
    return accumulate(in_set.begin(), in_set.end(), 0);
  };
  int K = Move(1);
  debug(K);
  int low = 2, high = (N / K) + 1;
  while (low < high) {
    int size = N - accumulate(deact.begin(), deact.end(), 0);
    int mid = low;
    int ls = K, rs = size - K;
    while (ls + K <= rs - K) {
      ls += K, rs -= K;
      ++mid;
    }
    int card = Move(mid);
    debug(mid, card);
    if (card == K * mid) {
      low = mid + 1;
      for (int i = 0; i < N; ++i) {
        if (in_set[i]) {
          deact[i] = true;
        }
      }
    } 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 228 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 5 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 5 ms 208 KB Output is correct
9 Correct 6 ms 208 KB Output is correct
10 Correct 3 ms 208 KB Output is correct
11 Correct 2 ms 208 KB Output is correct
12 Correct 4 ms 208 KB Output is correct
13 Correct 3 ms 208 KB Output is correct
14 Execution timed out 3073 ms 208 KB Time limit exceeded
15 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 228 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 5 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 5 ms 208 KB Output is correct
9 Correct 6 ms 208 KB Output is correct
10 Correct 3 ms 208 KB Output is correct
11 Correct 2 ms 208 KB Output is correct
12 Correct 4 ms 208 KB Output is correct
13 Correct 3 ms 208 KB Output is correct
14 Execution timed out 3073 ms 208 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 25 ms 208 KB Output is correct
8 Correct 21 ms 208 KB Output is correct
9 Partially correct 66 ms 208 KB Output is partially correct
10 Execution timed out 3014 ms 280 KB Time limit exceeded
11 Halted 0 ms 0 KB -