oj.uz

답안 #711982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711982 2023-03-17T20:02:28 Z stevancv Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 1000 ms 123312 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 = 1e6 + 2;
const int inf = 1e9;
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
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 33024 KB Output is correct
2 Correct 216 ms 50508 KB Output is correct
3 Correct 117 ms 47284 KB Output is correct
4 Correct 57 ms 30192 KB Output is correct
5 Correct 103 ms 35972 KB Output is correct
6 Correct 50 ms 33168 KB Output is correct
7 Correct 120 ms 47332 KB Output is correct
8 Correct 174 ms 51252 KB Output is correct
9 Correct 265 ms 53364 KB Output is correct
10 Correct 432 ms 54348 KB Output is correct
11 Correct 277 ms 49728 KB Output is correct
12 Correct 48 ms 29348 KB Output is correct
13 Correct 686 ms 57312 KB Output is correct
14 Correct 775 ms 57368 KB Output is correct
15 Correct 220 ms 49736 KB Output is correct
16 Correct 211 ms 50500 KB Output is correct
17 Correct 139 ms 35964 KB Output is correct
18 Correct 52 ms 30128 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 72 ms 59764 KB Execution killed with signal 11
2 Runtime error 92 ms 70412 KB Execution killed with signal 11
3 Execution timed out 1088 ms 66592 KB Time limit exceeded
4 Runtime error 116 ms 74892 KB Execution killed with signal 11
5 Runtime error 430 ms 110428 KB Execution killed with signal 11
6 Incorrect 237 ms 46860 KB Output isn't correct
7 Runtime error 87 ms 59792 KB Execution killed with signal 11
8 Runtime error 164 ms 75588 KB Execution killed with signal 11
9 Runtime error 406 ms 116980 KB Execution killed with signal 11
10 Execution timed out 1056 ms 65256 KB Time limit exceeded
11 Execution timed out 1081 ms 62128 KB Time limit exceeded
12 Runtime error 213 ms 96924 KB Execution killed with signal 11
13 Runtime error 56 ms 63864 KB Execution killed with signal 11
14 Runtime error 95 ms 74764 KB Execution killed with signal 11
15 Runtime error 596 ms 118056 KB Execution killed with signal 11
16 Runtime error 110 ms 70368 KB Execution killed with signal 11
17 Runtime error 299 ms 107192 KB Execution killed with signal 11
18 Incorrect 789 ms 65464 KB Output isn't correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 280 ms 114548 KB Execution killed with signal 11
2 Runtime error 377 ms 116272 KB Execution killed with signal 11
3 Runtime error 407 ms 116104 KB Execution killed with signal 11
4 Runtime error 173 ms 99200 KB Execution killed with signal 11
5 Runtime error 103 ms 71156 KB Execution killed with signal 11
6 Runtime error 276 ms 105804 KB Execution killed with signal 11
7 Runtime error 199 ms 104488 KB Execution killed with signal 11
8 Runtime error 297 ms 114540 KB Execution killed with signal 11
9 Runtime error 301 ms 114536 KB Execution killed with signal 11
10 Runtime error 191 ms 94944 KB Execution killed with signal 11
11 Runtime error 148 ms 87672 KB Execution killed with signal 11
12 Runtime error 273 ms 104932 KB Execution killed with signal 11
13 Runtime error 791 ms 120524 KB Execution killed with signal 11
14 Runtime error 396 ms 110656 KB Execution killed with signal 11
15 Runtime error 284 ms 107732 KB Execution killed with signal 11
16 Runtime error 327 ms 108868 KB Execution killed with signal 11
17 Runtime error 255 ms 108488 KB Execution killed with signal 11
18 Runtime error 426 ms 116364 KB Execution killed with signal 11
19 Runtime error 77 ms 75344 KB Execution killed with signal 11
20 Runtime error 367 ms 116096 KB Execution killed with signal 11
21 Runtime error 210 ms 106068 KB Execution killed with signal 11
22 Runtime error 348 ms 121824 KB Execution killed with signal 11
23 Runtime error 89 ms 68344 KB Execution killed with signal 11
24 Runtime error 71 ms 59916 KB Execution killed with signal 11
25 Runtime error 199 ms 97384 KB Execution killed with signal 11
26 Runtime error 208 ms 99116 KB Execution killed with signal 11
27 Runtime error 404 ms 123312 KB Execution killed with signal 11
28 Runtime error 79 ms 70604 KB Execution killed with signal 11
29 Runtime error 275 ms 118188 KB Execution killed with signal 11
30 Runtime error 244 ms 113332 KB Execution killed with signal 11
31 Runtime error 82 ms 73056 KB Execution killed with signal 11
32 Runtime error 134 ms 79416 KB Execution killed with signal 11
33 Runtime error 60 ms 54964 KB Execution killed with signal 11
34 Runtime error 212 ms 104384 KB Execution killed with signal 11
35 Runtime error 86 ms 72208 KB Execution killed with signal 11
36 Runtime error 394 ms 120596 KB Execution killed with signal 11
37 Runtime error 102 ms 71228 KB Execution killed with signal 11
38 Runtime error 259 ms 105804 KB Execution killed with signal 11
39 Runtime error 72 ms 63660 KB Execution killed with signal 11
40 Runtime error 231 ms 103256 KB Execution killed with signal 11
41 Runtime error 230 ms 109104 KB Execution killed with signal 11
42 Runtime error 294 ms 108368 KB Execution killed with signal 11