oj.uz

Submission #464759

# Submission time Handle Problem Language Result Execution time Memory
464759 2021-08-14T00:16:07 Z JovanB Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 537 ms 40652 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 10000000;

int dp[N+5];
int tren;
queue <pair <int, int>> q[2];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int m, qrs;
    cin >> m >> qrs;
    for(int i=1; i<=m; i++){
        int x;
        cin >> x;
        q[0].push({0, x});
    }
    for(int i=1; i<=N; i++){
        queue <int> divs;
        while(!q[0].empty()){
            int j, x;
            tie(j, x) = q[0].front();
            if(j + x < i){
                int g = j + x;
                while(g + x < i) g += x;
                q[(tren != dp[g])].push({g, x});
            }
            else if(j + x <= i) divs.push(x);
            else break;
            q[0].pop();
        }
        if(q[0].empty()) swap(q[0], q[1]), tren++;
        while(!q[0].empty()){
            int j, x;
            tie(j, x) = q[0].front();
            if(j + x < i){
                int g = j + x;
                while(g + x < i) g += x;
                q[(tren != dp[g])].push({g, x});
            }
            else if(j + x <= i) divs.push(x);
            else break;
            q[0].pop();
        }
        if(q[0].empty()) break;
        dp[i] = tren + 1;
        while(!divs.empty()) q[1].push({i, divs.front()}), divs.pop();
    }
    while(qrs--){
        int x;
        cin >> x;
        if(!dp[x]) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 446 ms 39444 KB Output is correct
3 Correct 13 ms 1356 KB Output is correct
4 Correct 431 ms 39512 KB Output is correct
5 Correct 468 ms 39448 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 13 ms 1300 KB Output is correct
8 Correct 50 ms 3856 KB Output is correct
9 Correct 495 ms 39468 KB Output is correct
10 Correct 475 ms 39360 KB Output is correct
11 Correct 468 ms 39492 KB Output is correct
12 Correct 430 ms 39492 KB Output is correct
13 Correct 460 ms 39492 KB Output is correct
14 Correct 459 ms 39460 KB Output is correct
15 Correct 455 ms 39364 KB Output is correct
16 Correct 447 ms 39364 KB Output is correct
17 Correct 456 ms 39392 KB Output is correct
18 Correct 434 ms 39372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 39492 KB Output is correct
2 Correct 436 ms 40264 KB Output is correct
3 Correct 457 ms 40004 KB Output is correct
4 Correct 429 ms 39404 KB Output is correct
5 Correct 473 ms 39876 KB Output is correct
6 Correct 424 ms 39412 KB Output is correct
7 Correct 426 ms 39684 KB Output is correct
8 Correct 441 ms 39364 KB Output is correct
9 Correct 465 ms 40008 KB Output is correct
10 Correct 460 ms 40060 KB Output is correct
11 Correct 469 ms 39672 KB Output is correct
12 Correct 441 ms 39600 KB Output is correct
13 Correct 418 ms 39364 KB Output is correct
14 Correct 430 ms 39444 KB Output is correct
15 Correct 449 ms 39756 KB Output is correct
16 Correct 459 ms 40212 KB Output is correct
17 Correct 443 ms 39444 KB Output is correct
18 Correct 456 ms 40324 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 39876 KB Output is correct
2 Correct 478 ms 39936 KB Output is correct
3 Correct 475 ms 40096 KB Output is correct
4 Correct 471 ms 39656 KB Output is correct
5 Correct 470 ms 40488 KB Output is correct
6 Correct 465 ms 39776 KB Output is correct
7 Correct 473 ms 40456 KB Output is correct
8 Correct 463 ms 39960 KB Output is correct
9 Correct 469 ms 40004 KB Output is correct
10 Correct 448 ms 39428 KB Output is correct
11 Correct 473 ms 39528 KB Output is correct
12 Correct 470 ms 39612 KB Output is correct
13 Correct 474 ms 39964 KB Output is correct
14 Correct 504 ms 39964 KB Output is correct
15 Correct 459 ms 39504 KB Output is correct
16 Correct 455 ms 39516 KB Output is correct
17 Correct 475 ms 39996 KB Output is correct
18 Correct 464 ms 40004 KB Output is correct
19 Correct 451 ms 39424 KB Output is correct
20 Correct 499 ms 39964 KB Output is correct
21 Correct 512 ms 40128 KB Output is correct
22 Correct 513 ms 40608 KB Output is correct
23 Correct 466 ms 39936 KB Output is correct
24 Correct 450 ms 39620 KB Output is correct
25 Correct 473 ms 39768 KB Output is correct
26 Correct 461 ms 39704 KB Output is correct
27 Correct 537 ms 40652 KB Output is correct
28 Correct 501 ms 39720 KB Output is correct
29 Correct 492 ms 40536 KB Output is correct
30 Correct 506 ms 40260 KB Output is correct
31 Correct 494 ms 39740 KB Output is correct
32 Correct 462 ms 39748 KB Output is correct
33 Correct 466 ms 39620 KB Output is correct
34 Correct 460 ms 40468 KB Output is correct
35 Correct 448 ms 39744 KB Output is correct
36 Correct 488 ms 40388 KB Output is correct
37 Correct 462 ms 40516 KB Output is correct
38 Correct 495 ms 39832 KB Output is correct
39 Correct 458 ms 39788 KB Output is correct
40 Correct 468 ms 39932 KB Output is correct
41 Correct 462 ms 40516 KB Output is correct
42 Correct 466 ms 39900 KB Output is correct