oj.uz

Submission #799383

# Submission time Handle Problem Language Result Execution time Memory
799383 2023-07-31T13:35:37 Z tch1cherin Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 514 ms 88468 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e7 + 5;
int fact[MAX_N] = {};
int dp[MAX_N] = {};
bool is_special[MAX_N] = {};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int M, Q;
  cin >> M >> Q;
  vector<int> primes(M);
  for (auto &v : primes) {
    cin >> v;
    is_special[v] = true;
  }
  sort(primes.begin(), primes.end());
  for (int i = 2; i < MAX_N; i++) {
    if (fact[i] == 0) {
      fact[i] = i;
      if (i < MAX_N / i) {
        for (int j = i * i; j < MAX_N; j += i) {
          fact[j] = i;
        }
      }
    }
  }
  int r0 = primes.back(), r1 = primes.back();
  dp[1] = 1;
  for (int i = 2; i < r0; i++) {
    dp[i] = 1;
    int t = i, max_f = -1;
    while (t > 1) {
      max_f = fact[t] > max_f && is_special[fact[t]] ? fact[t] : max_f;
      t /= fact[t];
    }
    r1 = max(r1, i + max_f);
  }
  fill(dp + r0, dp + MAX_N, INT_MAX);
  int val = 1;
  for (int i = r0; i < MAX_N; i++) {
    if (i >= r0) {
      r0 = r1;
      val++;
    }
    if (i >= r0) {
      break;
    }
    dp[i] = val;
    int t = i, max_f = -1;
    while (t > 1) {
      max_f = fact[t] > max_f && is_special[fact[t]] ? fact[t] : max_f;
      t /= fact[t];
    }
    r1 = max(r1, i + max_f);
  }
  while (Q--) {
    int n;
    cin >> n;
    if (dp[n] == INT_MAX) {
      cout << "oo\n";
    } else {
      cout << dp[n] << "\n";
    }
  }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 78544 KB Output is correct
2 Correct 485 ms 78608 KB Output is correct
3 Correct 125 ms 78512 KB Output is correct
4 Correct 491 ms 78656 KB Output is correct
5 Correct 485 ms 78592 KB Output is correct
6 Correct 120 ms 78512 KB Output is correct
7 Correct 125 ms 78544 KB Output is correct
8 Correct 145 ms 78540 KB Output is correct
9 Correct 471 ms 78600 KB Output is correct
10 Correct 479 ms 78608 KB Output is correct
11 Correct 481 ms 78620 KB Output is correct
12 Correct 484 ms 78612 KB Output is correct
13 Correct 470 ms 78756 KB Output is correct
14 Correct 478 ms 78592 KB Output is correct
15 Correct 487 ms 78540 KB Output is correct
16 Correct 474 ms 78612 KB Output is correct
17 Correct 471 ms 78660 KB Output is correct
18 Correct 477 ms 78656 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 79620 KB Output is correct
2 Correct 493 ms 88468 KB Output is correct
3 Correct 471 ms 80344 KB Output is correct
4 Correct 478 ms 78736 KB Output is correct
5 Correct 491 ms 80460 KB Output is correct
6 Correct 476 ms 78696 KB Output is correct
7 Correct 476 ms 79660 KB Output is correct
8 Correct 475 ms 78640 KB Output is correct
9 Correct 499 ms 80660 KB Output is correct
10 Correct 474 ms 80460 KB Output is correct
11 Correct 501 ms 79524 KB Output is correct
12 Correct 513 ms 78672 KB Output is correct
13 Correct 473 ms 79252 KB Output is correct
14 Correct 477 ms 78632 KB Output is correct
15 Correct 488 ms 79952 KB Output is correct
16 Correct 506 ms 88376 KB Output is correct
17 Correct 466 ms 78552 KB Output is correct
18 Correct 495 ms 81756 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 80416 KB Output is correct
2 Correct 477 ms 80036 KB Output is correct
3 Correct 479 ms 80356 KB Output is correct
4 Correct 505 ms 79608 KB Output is correct
5 Correct 496 ms 84960 KB Output is correct
6 Correct 509 ms 79772 KB Output is correct
7 Correct 500 ms 82504 KB Output is correct
8 Correct 493 ms 80416 KB Output is correct
9 Correct 489 ms 80416 KB Output is correct
10 Correct 487 ms 78812 KB Output is correct
11 Correct 493 ms 79056 KB Output is correct
12 Correct 486 ms 78924 KB Output is correct
13 Correct 484 ms 80256 KB Output is correct
14 Correct 481 ms 79820 KB Output is correct
15 Correct 476 ms 78952 KB Output is correct
16 Correct 475 ms 78968 KB Output is correct
17 Correct 488 ms 79948 KB Output is correct
18 Correct 479 ms 80024 KB Output is correct
19 Correct 487 ms 79636 KB Output is correct
20 Correct 470 ms 80332 KB Output is correct
21 Correct 485 ms 79928 KB Output is correct
22 Correct 504 ms 82124 KB Output is correct
23 Correct 500 ms 80856 KB Output is correct
24 Correct 498 ms 79640 KB Output is correct
25 Correct 504 ms 79668 KB Output is correct
26 Correct 509 ms 79740 KB Output is correct
27 Correct 476 ms 81612 KB Output is correct
28 Correct 487 ms 79796 KB Output is correct
29 Correct 514 ms 82112 KB Output is correct
30 Correct 508 ms 81308 KB Output is correct
31 Correct 496 ms 79816 KB Output is correct
32 Correct 509 ms 79712 KB Output is correct
33 Correct 492 ms 79692 KB Output is correct
34 Correct 495 ms 82416 KB Output is correct
35 Correct 494 ms 79816 KB Output is correct
36 Correct 500 ms 81952 KB Output is correct
37 Correct 496 ms 85140 KB Output is correct
38 Correct 503 ms 79784 KB Output is correct
39 Correct 495 ms 79796 KB Output is correct
40 Correct 514 ms 79832 KB Output is correct
41 Correct 505 ms 83512 KB Output is correct
42 Correct 477 ms 79784 KB Output is correct