oj.uz

Submission #734041

# Submission time Handle Problem Language Result Execution time Memory
734041 2023-05-01T14:18:15 Z MilosMilutinovic Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 728 ms 157456 KB 
/**
 *    author:  wxhtzdy
 *    created: 01.05.2023 15:53:44
**/
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  cin >> n >> q;
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }           
  const int MAX = 2e7 + 5;
  vector<int> mn(MAX, MAX);
  for (int i = 0; i < n; i++) {
    for (int k = 0; p[i] * (k + 1) < MAX; k++) {
      mn[(k + 1) * p[i] - 1] = min(mn[(k + 1) * p[i] - 1], k * p[i]);
    }
  }
  for (int i = MAX - 1; i > 0; i--) {
    mn[i - 1] = min(mn[i - 1], mn[i]);
  }
  vector<int> ans(MAX);
  for (int i = 1; i < MAX; i++) {
    if (mn[i] == i || mn[i] == MAX) {
      ans[i] = MAX;
    } else {
      ans[i] = ans[mn[i]] + 1;
    }
  }
  while (q--) {
    int x;
    cin >> x;     
    if (ans[x] >= MAX) {
      cout << "oo" << '\n';     
    } else {
      cout << ans[x] << '\n';
    }
  }                                                          
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 156952 KB Output is correct
2 Correct 220 ms 156796 KB Output is correct
3 Correct 201 ms 156796 KB Output is correct
4 Correct 127 ms 156880 KB Output is correct
5 Correct 158 ms 156876 KB Output is correct
6 Correct 204 ms 156872 KB Output is correct
7 Correct 185 ms 156924 KB Output is correct
8 Correct 215 ms 156796 KB Output is correct
9 Correct 259 ms 156748 KB Output is correct
10 Correct 288 ms 156768 KB Output is correct
11 Correct 244 ms 156800 KB Output is correct
12 Correct 124 ms 156764 KB Output is correct
13 Correct 484 ms 156820 KB Output is correct
14 Correct 480 ms 156804 KB Output is correct
15 Correct 244 ms 156792 KB Output is correct
16 Correct 230 ms 156784 KB Output is correct
17 Correct 193 ms 156912 KB Output is correct
18 Correct 134 ms 156800 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 156880 KB Output is correct
2 Correct 178 ms 157240 KB Output is correct
3 Correct 628 ms 157088 KB Output is correct
4 Correct 229 ms 156816 KB Output is correct
5 Correct 370 ms 157048 KB Output is correct
6 Correct 202 ms 156876 KB Output is correct
7 Correct 164 ms 156848 KB Output is correct
8 Correct 198 ms 156880 KB Output is correct
9 Correct 476 ms 157156 KB Output is correct
10 Correct 586 ms 157132 KB Output is correct
11 Correct 570 ms 156964 KB Output is correct
12 Correct 344 ms 156820 KB Output is correct
13 Correct 153 ms 156824 KB Output is correct
14 Correct 224 ms 156812 KB Output is correct
15 Correct 521 ms 156960 KB Output is correct
16 Correct 181 ms 157132 KB Output is correct
17 Correct 478 ms 156884 KB Output is correct
18 Correct 472 ms 157196 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 157196 KB Output is correct
2 Correct 603 ms 157084 KB Output is correct
3 Correct 600 ms 157200 KB Output is correct
4 Correct 356 ms 157068 KB Output is correct
5 Correct 208 ms 157436 KB Output is correct
6 Correct 482 ms 157088 KB Output is correct
7 Correct 367 ms 157316 KB Output is correct
8 Correct 484 ms 157124 KB Output is correct
9 Correct 500 ms 157096 KB Output is correct
10 Correct 348 ms 156876 KB Output is correct
11 Correct 307 ms 156852 KB Output is correct
12 Correct 428 ms 156956 KB Output is correct
13 Correct 576 ms 157260 KB Output is correct
14 Correct 327 ms 157324 KB Output is correct
15 Correct 467 ms 156944 KB Output is correct
16 Correct 531 ms 156956 KB Output is correct
17 Correct 426 ms 157084 KB Output is correct
18 Correct 633 ms 157060 KB Output is correct
19 Correct 195 ms 156896 KB Output is correct
20 Correct 649 ms 157148 KB Output is correct
21 Correct 387 ms 157388 KB Output is correct
22 Correct 619 ms 157456 KB Output is correct
23 Correct 225 ms 157172 KB Output is correct
24 Correct 192 ms 157180 KB Output is correct
25 Correct 396 ms 157088 KB Output is correct
26 Correct 357 ms 157064 KB Output is correct
27 Correct 671 ms 157328 KB Output is correct
28 Correct 192 ms 157132 KB Output is correct
29 Correct 521 ms 157384 KB Output is correct
30 Correct 476 ms 157332 KB Output is correct
31 Correct 218 ms 157080 KB Output is correct
32 Correct 270 ms 157156 KB Output is correct
33 Correct 157 ms 157060 KB Output is correct
34 Correct 417 ms 157356 KB Output is correct
35 Correct 250 ms 157076 KB Output is correct
36 Correct 728 ms 157408 KB Output is correct
37 Correct 246 ms 157396 KB Output is correct
38 Correct 625 ms 157164 KB Output is correct
39 Correct 201 ms 157140 KB Output is correct
40 Correct 419 ms 157132 KB Output is correct
41 Correct 351 ms 157324 KB Output is correct
42 Correct 547 ms 157200 KB Output is correct