oj.uz

답안 #711743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711743 2023-03-17T11:55:25 Z stevancv Brunhilda’s Birthday (BOI13_brunhilda) C++14
17.7778 / 100
 121 ms 22048 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 1e5 + 2;
const int inf = 2e9;
vector<int> primes[M];
int idx[M], ans[N], koji[M], dp[M];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    multiset<pair<int, int>> s;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        assert(s.find({0, x}) == s.end());
        s.insert({0, x});
        for (int j = x; j < M; j += x) primes[j].push_back(x);
    }
    for (int i = 1; i <= q; i++) {
        int x; cin >> x;
        idx[x] = i;
    }
    for (int i = 1; i < M; i++) {
        dp[i] = inf;
        for (int j : primes[i]) {
            s.erase({koji[j], j});
        }
        if (!s.empty()) dp[i] = s.begin()->first + 1;
        if (idx[i] != 0) ans[idx[i]] = dp[i];
        for (int j : primes[i]) {
            s.insert({dp[i], j});
            koji[j] = dp[i];
        }
    }
    for (int i = 1; i <= q; i++) {
        if (ans[i] == inf) cout << "oo" << en;
        else cout << ans[i] << en;
    }
    return 0;
}

Subtask #1
17.7777777778 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 3668 KB Output isn't correct
2 Correct 19 ms 5396 KB Output is correct
3 Correct 13 ms 4948 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 11 ms 3808 KB Output is correct
6 Incorrect 5 ms 3540 KB Output isn't correct
7 Correct 15 ms 5108 KB Output is correct
8 Correct 16 ms 5460 KB Output is correct
9 Correct 26 ms 5588 KB Output is correct
10 Correct 30 ms 5716 KB Output is correct
11 Correct 23 ms 5280 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 62 ms 6044 KB Output is correct
14 Correct 58 ms 6040 KB Output is correct
15 Correct 22 ms 5204 KB Output is correct
16 Correct 20 ms 5288 KB Output is correct
17 Correct 13 ms 3992 KB Output is correct
18 Correct 8 ms 3412 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 7252 KB Execution killed with signal 11
2 Runtime error 44 ms 15128 KB Execution killed with signal 11
3 Runtime error 42 ms 18320 KB Execution killed with signal 11
4 Runtime error 7 ms 8204 KB Execution killed with signal 11
5 Runtime error 34 ms 15380 KB Execution killed with signal 11
6 Runtime error 12 ms 9100 KB Execution killed with signal 11
7 Runtime error 9 ms 7244 KB Execution killed with signal 11
8 Runtime error 9 ms 7764 KB Execution killed with signal 11
9 Incorrect 102 ms 9792 KB Output isn't correct
10 Runtime error 47 ms 18252 KB Execution killed with signal 11
11 Runtime error 32 ms 15444 KB Execution killed with signal 11
12 Runtime error 11 ms 10324 KB Execution killed with signal 11
13 Runtime error 7 ms 6996 KB Execution killed with signal 11
14 Runtime error 8 ms 8148 KB Execution killed with signal 11
15 Runtime error 40 ms 15332 KB Execution killed with signal 11
16 Runtime error 42 ms 15100 KB Execution killed with signal 11
17 Runtime error 17 ms 11476 KB Execution killed with signal 11
18 Runtime error 121 ms 22048 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 35 ms 16164 KB Execution killed with signal 11
2 Runtime error 36 ms 16632 KB Execution killed with signal 11
3 Runtime error 36 ms 16484 KB Execution killed with signal 11
4 Runtime error 13 ms 10836 KB Execution killed with signal 11
5 Runtime error 44 ms 15596 KB Execution killed with signal 11
6 Runtime error 16 ms 11960 KB Execution killed with signal 11
7 Runtime error 52 ms 19424 KB Execution killed with signal 11
8 Runtime error 32 ms 16076 KB Execution killed with signal 11
9 Runtime error 36 ms 16060 KB Execution killed with signal 11
10 Runtime error 18 ms 10880 KB Execution killed with signal 11
11 Runtime error 11 ms 9812 KB Execution killed with signal 11
12 Runtime error 23 ms 11600 KB Execution killed with signal 11
13 Runtime error 28 ms 14444 KB Execution killed with signal 11
14 Runtime error 19 ms 11384 KB Execution killed with signal 11
15 Runtime error 18 ms 11852 KB Execution killed with signal 11
16 Runtime error 20 ms 12192 KB Execution killed with signal 11
17 Runtime error 29 ms 15096 KB Execution killed with signal 11
18 Runtime error 34 ms 16620 KB Execution killed with signal 11
19 Runtime error 7 ms 8276 KB Execution killed with signal 11
20 Runtime error 35 ms 16376 KB Execution killed with signal 11
21 Runtime error 13 ms 10952 KB Execution killed with signal 11
22 Runtime error 55 ms 21120 KB Execution killed with signal 11
23 Runtime error 18 ms 9428 KB Execution killed with signal 11
24 Runtime error 8 ms 6484 KB Execution killed with signal 11
25 Runtime error 18 ms 10580 KB Execution killed with signal 11
26 Runtime error 19 ms 10836 KB Execution killed with signal 11
27 Runtime error 57 ms 21216 KB Execution killed with signal 11
28 Runtime error 6 ms 7636 KB Execution killed with signal 11
29 Runtime error 52 ms 20684 KB Execution killed with signal 11
30 Runtime error 38 ms 17620 KB Execution killed with signal 11
31 Runtime error 8 ms 8064 KB Execution killed with signal 11
32 Runtime error 9 ms 8708 KB Execution killed with signal 11
33 Runtime error 5 ms 5972 KB Execution killed with signal 11
34 Runtime error 49 ms 19156 KB Execution killed with signal 11
35 Runtime error 7 ms 7896 KB Execution killed with signal 11
36 Runtime error 55 ms 20112 KB Execution killed with signal 11
37 Runtime error 58 ms 15556 KB Execution killed with signal 11
38 Runtime error 22 ms 11892 KB Execution killed with signal 11
39 Runtime error 7 ms 6924 KB Execution killed with signal 11
40 Runtime error 17 ms 11840 KB Execution killed with signal 11
41 Runtime error 52 ms 19748 KB Execution killed with signal 11
42 Runtime error 18 ms 11568 KB Execution killed with signal 11