Submission #734025

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
734025	2023-05-01T14:03:45 Z	MilosMilutinovic	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	80.3175 / 100	342 ms	80700 KB

brunhilda

/**
 *    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 = 1e7 + 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	75 ms	78540 KB	Output is correct
2	Correct	123 ms	78496 KB	Output is correct
3	Correct	93 ms	78552 KB	Output is correct
4	Correct	66 ms	78540 KB	Output is correct
5	Correct	96 ms	78608 KB	Output is correct
6	Correct	68 ms	78540 KB	Output is correct
7	Correct	97 ms	78536 KB	Output is correct
8	Correct	105 ms	78496 KB	Output is correct
9	Correct	126 ms	78492 KB	Output is correct
10	Correct	150 ms	78524 KB	Output is correct
11	Correct	127 ms	78556 KB	Output is correct
12	Correct	63 ms	78504 KB	Output is correct
13	Correct	232 ms	78536 KB	Output is correct
14	Correct	239 ms	78556 KB	Output is correct
15	Correct	117 ms	78500 KB	Output is correct
16	Correct	113 ms	78464 KB	Output is correct
17	Correct	91 ms	78540 KB	Output is correct
18	Correct	66 ms	78644 KB	Output is correct

Subtask #2

18.8888888889 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	86 ms	78708 KB	Output is correct
2	Correct	94 ms	79636 KB	Output is correct
3	Correct	300 ms	79240 KB	Output is correct
4	Correct	112 ms	78524 KB	Output is correct
5	Correct	192 ms	79144 KB	Output is correct
6	Correct	105 ms	78500 KB	Output is correct
7	Correct	84 ms	78668 KB	Output is correct
8	Correct	101 ms	78504 KB	Output is correct
9	Correct	228 ms	79268 KB	Output is correct
10	Correct	325 ms	79236 KB	Output is correct
11	Incorrect	297 ms	78912 KB	Output isn't correct
12	Correct	145 ms	78512 KB	Output is correct
13	Correct	86 ms	78524 KB	Output is correct
14	Correct	135 ms	78496 KB	Output is correct
15	Correct	233 ms	78988 KB	Output is correct
16	Correct	94 ms	79540 KB	Output is correct
17	Correct	257 ms	78512 KB	Output is correct
18	Correct	221 ms	79608 KB	Output is correct

Subtask #3

41.4285714286 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	268 ms	79436 KB	Output is correct
2	Correct	294 ms	79324 KB	Output is correct
3	Correct	315 ms	79696 KB	Output is correct
4	Incorrect	186 ms	79512 KB	Output isn't correct
5	Incorrect	121 ms	80700 KB	Output isn't correct
6	Correct	239 ms	79620 KB	Output is correct
7	Correct	190 ms	80204 KB	Output is correct
8	Correct	241 ms	79496 KB	Output is correct
9	Correct	288 ms	79436 KB	Output is correct
10	Correct	187 ms	78744 KB	Output is correct
11	Incorrect	165 ms	78756 KB	Output isn't correct
12	Correct	262 ms	78760 KB	Output is correct
13	Correct	326 ms	79844 KB	Output is correct
14	Correct	199 ms	79820 KB	Output is correct
15	Incorrect	258 ms	78880 KB	Output isn't correct
16	Correct	293 ms	79008 KB	Output is correct
17	Correct	296 ms	79180 KB	Output is correct
18	Correct	293 ms	79400 KB	Output is correct
19	Incorrect	91 ms	78808 KB	Output isn't correct
20	Correct	312 ms	79700 KB	Output is correct
21	Incorrect	199 ms	79944 KB	Output isn't correct
22	Correct	316 ms	80660 KB	Output is correct
23	Correct	130 ms	79880 KB	Output is correct
24	Correct	100 ms	79576 KB	Output is correct
25	Correct	205 ms	79640 KB	Output is correct
26	Incorrect	180 ms	79436 KB	Output isn't correct
27	Correct	342 ms	80172 KB	Output is correct
28	Incorrect	107 ms	79568 KB	Output isn't correct
29	Correct	276 ms	80660 KB	Output is correct
30	Correct	247 ms	80420 KB	Output is correct
31	Correct	122 ms	79528 KB	Output is correct
32	Incorrect	136 ms	79564 KB	Output isn't correct
33	Incorrect	92 ms	79424 KB	Output isn't correct
34	Correct	202 ms	80240 KB	Output is correct
35	Incorrect	107 ms	79692 KB	Output isn't correct
36	Correct	333 ms	80496 KB	Output is correct
37	Incorrect	119 ms	80656 KB	Output isn't correct
38	Correct	264 ms	79536 KB	Output is correct
39	Incorrect	114 ms	79588 KB	Output isn't correct
40	Correct	203 ms	79556 KB	Output is correct
41	Correct	180 ms	80256 KB	Output is correct
42	Correct	276 ms	79728 KB	Output is correct