답안 #734619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734619 2023-05-02T17:19:17 Z DAleksa Brunhilda’s Birthday (BOI13_brunhilda) C++17
28.7302 / 100
751 ms 262144 KB
#include <bits/stdc++.h>

using namespace std;

const int N = 15000000 + 10;
int n, q;
vector<int> p;
vector<int> v;
int cnt[N];
int prime[N];
int prv[N];
int dp[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    p.resize(n);
    for(int i = 0; i < n; i++) cin >> p[i];
    for(int i = p.size() - 1; i >= 0; i--) {
        for(int j = p[i]; j < N; j += p[i]) {
            if(prime[j] == 0) {
                cnt[j]++;
                prime[j] = p[i];
            }
        }
    }
    cnt[0]++;
    prime[0] = p.back();
    for(int i = 0; i < N; i++) for(int j = 0; j < cnt[i]; j++) v.push_back(i);
    int j = 0;
    for(int i = 1; i < N; i++) {
        while(v[j] + prime[v[j]] <= i) j++;
        prv[i] = v[j];
    }
    for(int i = 1; i < N; i++) {
        if(prv[i] == i) dp[i] = -1;
        else dp[i] = dp[prv[i]] + 1;
    }
    while(q--) {
        int x;
        cin >> x;
        if(x < p.back()) cout << "1\n";
        else if(dp[x] == -1) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 230 ms 245136 KB Output isn't correct
2 Runtime error 340 ms 262144 KB Execution killed with signal 9
3 Runtime error 302 ms 262144 KB Execution killed with signal 9
4 Correct 229 ms 239640 KB Output is correct
5 Correct 286 ms 250732 KB Output is correct
6 Incorrect 247 ms 245304 KB Output isn't correct
7 Runtime error 331 ms 262144 KB Execution killed with signal 9
8 Runtime error 325 ms 262144 KB Execution killed with signal 9
9 Runtime error 418 ms 262144 KB Execution killed with signal 9
10 Runtime error 430 ms 262144 KB Execution killed with signal 9
11 Runtime error 421 ms 262144 KB Execution killed with signal 9
12 Correct 175 ms 238344 KB Output is correct
13 Runtime error 622 ms 262144 KB Execution killed with signal 9
14 Runtime error 599 ms 262144 KB Execution killed with signal 9
15 Runtime error 411 ms 262144 KB Execution killed with signal 9
16 Runtime error 347 ms 262144 KB Execution killed with signal 9
17 Correct 293 ms 250592 KB Output is correct
18 Correct 186 ms 239512 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 275 ms 245200 KB Output is correct
2 Correct 285 ms 248788 KB Output is correct
3 Runtime error 751 ms 262144 KB Execution killed with signal 9
4 Correct 367 ms 258932 KB Output is correct
5 Runtime error 553 ms 262144 KB Execution killed with signal 9
6 Runtime error 354 ms 262144 KB Execution killed with signal 9
7 Correct 249 ms 245108 KB Output is correct
8 Correct 354 ms 256308 KB Output is correct
9 Runtime error 603 ms 262144 KB Execution killed with signal 9
10 Runtime error 619 ms 262144 KB Execution killed with signal 9
11 Runtime error 702 ms 262144 KB Execution killed with signal 9
12 Runtime error 522 ms 262144 KB Execution killed with signal 9
13 Correct 245 ms 249612 KB Output is correct
14 Correct 365 ms 258920 KB Output is correct
15 Runtime error 617 ms 262144 KB Execution killed with signal 9
16 Correct 281 ms 248796 KB Output is correct
17 Runtime error 640 ms 262144 KB Execution killed with signal 9
18 Runtime error 551 ms 262144 KB Execution killed with signal 9
# 결과 실행 시간 메모리 Grader output
1 Runtime error 532 ms 262144 KB Execution killed with signal 9
2 Runtime error 585 ms 262144 KB Execution killed with signal 9
3 Runtime error 623 ms 262144 KB Execution killed with signal 9
4 Runtime error 460 ms 262144 KB Execution killed with signal 9
5 Correct 288 ms 249860 KB Output is correct
6 Runtime error 522 ms 262144 KB Execution killed with signal 9
7 Runtime error 506 ms 262144 KB Execution killed with signal 9
8 Runtime error 523 ms 262144 KB Execution killed with signal 9
9 Runtime error 529 ms 262144 KB Execution killed with signal 9
10 Runtime error 485 ms 262144 KB Execution killed with signal 9
11 Runtime error 457 ms 262144 KB Execution killed with signal 9
12 Runtime error 522 ms 262144 KB Execution killed with signal 9
13 Runtime error 566 ms 262144 KB Execution killed with signal 9
14 Runtime error 434 ms 262144 KB Execution killed with signal 9
15 Runtime error 522 ms 262144 KB Execution killed with signal 9
16 Runtime error 567 ms 262144 KB Execution killed with signal 9
17 Runtime error 514 ms 262144 KB Execution killed with signal 9
18 Runtime error 599 ms 262144 KB Execution killed with signal 9
19 Correct 254 ms 260008 KB Output is correct
20 Runtime error 601 ms 262144 KB Execution killed with signal 9
21 Runtime error 455 ms 262144 KB Execution killed with signal 9
22 Runtime error 612 ms 262144 KB Execution killed with signal 9
23 Correct 345 ms 251752 KB Output is correct
24 Correct 261 ms 246188 KB Output is correct
25 Runtime error 502 ms 262144 KB Execution killed with signal 9
26 Runtime error 488 ms 262144 KB Execution killed with signal 9
27 Runtime error 615 ms 262144 KB Execution killed with signal 9
28 Correct 308 ms 256244 KB Output is correct
29 Runtime error 564 ms 262144 KB Execution killed with signal 9
30 Runtime error 531 ms 262144 KB Execution killed with signal 9
31 Correct 326 ms 257832 KB Output is correct
32 Runtime error 358 ms 262144 KB Execution killed with signal 9
33 Correct 210 ms 241772 KB Output is correct
34 Runtime error 498 ms 262144 KB Execution killed with signal 9
35 Correct 304 ms 257296 KB Output is correct
36 Runtime error 588 ms 262144 KB Execution killed with signal 9
37 Correct 294 ms 249864 KB Output is correct
38 Runtime error 534 ms 262144 KB Execution killed with signal 9
39 Correct 292 ms 249244 KB Output is correct
40 Runtime error 503 ms 262144 KB Execution killed with signal 9
41 Runtime error 477 ms 262144 KB Execution killed with signal 9
42 Runtime error 564 ms 262144 KB Execution killed with signal 9