oj.uz

답안 #711737

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711737 2023-03-17T11:52:41 Z stevancv Brunhilda’s Birthday (BOI13_brunhilda) C++14
17.7778 / 100
 142 ms 21840 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;
        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 18 ms 5364 KB Output is correct
3 Correct 11 ms 4948 KB Output is correct
4 Correct 6 ms 3412 KB Output is correct
5 Correct 11 ms 3824 KB Output is correct
6 Incorrect 6 ms 3576 KB Output isn't correct
7 Correct 14 ms 5076 KB Output is correct
8 Correct 33 ms 5348 KB Output is correct
9 Correct 25 ms 5584 KB Output is correct
10 Correct 31 ms 5648 KB Output is correct
11 Correct 22 ms 5196 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 61 ms 6060 KB Output is correct
14 Correct 54 ms 6092 KB Output is correct
15 Correct 22 ms 5184 KB Output is correct
16 Correct 23 ms 5348 KB Output is correct
17 Correct 11 ms 4052 KB Output is correct
18 Correct 7 ms 3452 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 7296 KB Execution killed with signal 11
2 Runtime error 34 ms 15656 KB Execution killed with signal 11
3 Runtime error 114 ms 20296 KB Execution killed with signal 6
4 Runtime error 7 ms 8192 KB Execution killed with signal 11
5 Runtime error 31 ms 15612 KB Execution killed with signal 11
6 Runtime error 10 ms 9172 KB Execution killed with signal 11
7 Runtime error 10 ms 7244 KB Execution killed with signal 11
8 Runtime error 7 ms 7744 KB Execution killed with signal 11
9 Runtime error 35 ms 18044 KB Execution killed with signal 11
10 Runtime error 44 ms 18644 KB Execution killed with signal 11
11 Runtime error 28 ms 15608 KB Execution killed with signal 11
12 Runtime error 12 ms 10368 KB Execution killed with signal 11
13 Runtime error 7 ms 6996 KB Execution killed with signal 11
14 Runtime error 8 ms 8192 KB Execution killed with signal 11
15 Runtime error 25 ms 15484 KB Execution killed with signal 11
16 Runtime error 42 ms 17304 KB Execution killed with signal 11
17 Runtime error 16 ms 11476 KB Execution killed with signal 11
18 Runtime error 42 ms 21144 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 16472 KB Execution killed with signal 11
2 Runtime error 41 ms 16996 KB Execution killed with signal 11
3 Runtime error 36 ms 16844 KB Execution killed with signal 11
4 Runtime error 12 ms 10876 KB Execution killed with signal 11
5 Runtime error 39 ms 16456 KB Execution killed with signal 11
6 Runtime error 22 ms 12132 KB Execution killed with signal 11
7 Runtime error 43 ms 19912 KB Execution killed with signal 11
8 Runtime error 32 ms 16444 KB Execution killed with signal 11
9 Runtime error 32 ms 16460 KB Execution killed with signal 11
10 Runtime error 13 ms 10836 KB Execution killed with signal 11
11 Runtime error 12 ms 9820 KB Execution killed with signal 11
12 Runtime error 20 ms 11772 KB Execution killed with signal 11
13 Incorrect 89 ms 8440 KB Output isn't correct
14 Runtime error 12 ms 10708 KB Execution killed with signal 11
15 Runtime error 17 ms 11904 KB Execution killed with signal 11
16 Runtime error 18 ms 12332 KB Execution killed with signal 11
17 Runtime error 33 ms 15416 KB Execution killed with signal 11
18 Runtime error 33 ms 16920 KB Execution killed with signal 11
19 Runtime error 8 ms 8404 KB Execution killed with signal 11
20 Runtime error 43 ms 16788 KB Execution killed with signal 11
21 Runtime error 14 ms 10880 KB Execution killed with signal 11
22 Runtime error 49 ms 21840 KB Execution killed with signal 11
23 Runtime error 14 ms 9660 KB Execution killed with signal 11
24 Runtime error 6 ms 6484 KB Execution killed with signal 11
25 Runtime error 16 ms 10708 KB Execution killed with signal 11
26 Runtime error 12 ms 10836 KB Execution killed with signal 11
27 Incorrect 142 ms 12452 KB Output isn't correct
28 Runtime error 7 ms 7552 KB Execution killed with signal 11
29 Runtime error 41 ms 21500 KB Execution killed with signal 11
30 Runtime error 30 ms 17944 KB Execution killed with signal 11
31 Runtime error 8 ms 8064 KB Execution killed with signal 11
32 Runtime error 12 ms 8700 KB Execution killed with signal 11
33 Runtime error 5 ms 5972 KB Execution killed with signal 11
34 Runtime error 49 ms 19884 KB Execution killed with signal 11
35 Runtime error 11 ms 7940 KB Execution killed with signal 11
36 Runtime error 53 ms 20876 KB Execution killed with signal 11
37 Runtime error 41 ms 16452 KB Execution killed with signal 11
38 Runtime error 24 ms 12080 KB Execution killed with signal 11
39 Runtime error 6 ms 7040 KB Execution killed with signal 11
40 Runtime error 23 ms 11904 KB Execution killed with signal 11
41 Runtime error 43 ms 20632 KB Execution killed with signal 11
42 Runtime error 18 ms 11596 KB Execution killed with signal 11