oj.uz

Submission #283232

# Submission time Handle Problem Language Result Execution time Memory
283232 2020-08-25T11:47:54 Z Atill83 Brunhilda’s Birthday (BOI13_brunhilda) C++14
48.0952 / 100
 1000 ms 40472 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 1e7+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll m, q;
ll p[(int)1e5 + 5];
int ans[MAXN];



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>m>>q;
    memset(ans, 0x7f, sizeof(ans));
    for(int i = 0; i < m; i++){
        cin>>p[i];
    }

    for(int i = 1; i < p[m - 1]; i++){
        ans[i] = 1;
    }

    for(int i = p[m - 1]; i <= 1e7; i++){
        //int mnI = -1;
        for(int j = m - 1; j >= max(m - 10, 0LL); j--){
            if(i % p[j] == 0) continue;
            if(ans[i - i % p[j]] + 1 < ans[i]){
                ans[i] = ans[i - i % p[j]] + 1;
                //mnI = j;
            }
        }
        //cout<<ans[i]<<" "<<mnI<<endl;
    }

    for(int i = 0; i < q; i++){
        int n;
        cin>>n;
        if(ans[n] >= 2139062143){
            cout<<"oo"<<endl;
        }else{
            cout<<ans[n]<<endl;
        }
    }

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
15.5555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 39424 KB Output is correct
2 Correct 805 ms 39544 KB Output is correct
3 Correct 482 ms 39544 KB Output is correct
4 Incorrect 741 ms 39544 KB Output isn't correct
5 Correct 886 ms 39548 KB Output is correct
6 Correct 294 ms 39532 KB Output is correct
7 Correct 486 ms 39544 KB Output is correct
8 Correct 568 ms 39544 KB Output is correct
9 Execution timed out 1006 ms 39524 KB Time limit exceeded
10 Correct 851 ms 39672 KB Output is correct
11 Correct 850 ms 39528 KB Output is correct
12 Correct 740 ms 39544 KB Output is correct
13 Correct 694 ms 39424 KB Output is correct
14 Correct 700 ms 39544 KB Output is correct
15 Correct 793 ms 39424 KB Output is correct
16 Correct 791 ms 39544 KB Output is correct
17 Incorrect 792 ms 39544 KB Output isn't correct
18 Incorrect 729 ms 39544 KB Output isn't correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 39640 KB Output is correct
2 Correct 91 ms 40184 KB Output is correct
3 Correct 462 ms 40184 KB Output is correct
4 Incorrect 647 ms 39672 KB Output isn't correct
5 Correct 519 ms 40056 KB Output is correct
6 Incorrect 643 ms 39544 KB Output isn't correct
7 Correct 539 ms 39672 KB Output is correct
8 Incorrect 683 ms 39540 KB Output isn't correct
9 Correct 514 ms 40088 KB Output is correct
10 Correct 457 ms 40184 KB Output is correct
11 Incorrect 568 ms 39928 KB Output isn't correct
12 Incorrect 654 ms 39548 KB Output isn't correct
13 Incorrect 579 ms 39672 KB Output isn't correct
14 Incorrect 635 ms 39676 KB Output isn't correct
15 Correct 550 ms 39856 KB Output is correct
16 Correct 94 ms 40184 KB Output is correct
17 Correct 671 ms 39672 KB Output is correct
18 Incorrect 319 ms 40184 KB Output isn't correct

Subtask #3
21.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 39928 KB Output is correct
2 Incorrect 563 ms 39936 KB Output isn't correct
3 Correct 554 ms 40056 KB Output is correct
4 Incorrect 659 ms 39928 KB Output isn't correct
5 Correct 352 ms 40440 KB Output is correct
6 Incorrect 661 ms 39928 KB Output isn't correct
7 Correct 431 ms 40312 KB Output is correct
8 Correct 555 ms 39924 KB Output is correct
9 Correct 548 ms 39928 KB Output is correct
10 Incorrect 640 ms 39676 KB Output isn't correct
11 Incorrect 642 ms 39672 KB Output isn't correct
12 Incorrect 648 ms 39588 KB Output isn't correct
13 Incorrect 593 ms 40020 KB Output isn't correct
14 Incorrect 866 ms 40056 KB Output isn't correct
15 Incorrect 653 ms 39544 KB Output isn't correct
16 Incorrect 648 ms 39680 KB Output isn't correct
17 Incorrect 555 ms 39884 KB Output isn't correct
18 Incorrect 563 ms 40056 KB Output isn't correct
19 Incorrect 558 ms 39552 KB Output isn't correct
20 Correct 551 ms 40056 KB Output is correct
21 Incorrect 788 ms 40056 KB Output isn't correct
22 Correct 532 ms 40440 KB Output is correct
23 Incorrect 560 ms 39896 KB Output isn't correct
24 Incorrect 662 ms 39800 KB Output isn't correct
25 Incorrect 686 ms 39928 KB Output isn't correct
26 Incorrect 661 ms 39800 KB Output isn't correct
27 Correct 502 ms 40312 KB Output is correct
28 Incorrect 643 ms 39804 KB Output isn't correct
29 Correct 529 ms 40440 KB Output is correct
30 Correct 567 ms 40312 KB Output is correct
31 Incorrect 613 ms 39804 KB Output isn't correct
32 Incorrect 674 ms 39808 KB Output isn't correct
33 Incorrect 645 ms 39800 KB Output isn't correct
34 Correct 429 ms 40312 KB Output is correct
35 Incorrect 650 ms 39928 KB Output isn't correct
36 Correct 528 ms 40360 KB Output is correct
37 Correct 354 ms 40472 KB Output is correct
38 Incorrect 665 ms 39844 KB Output isn't correct
39 Incorrect 663 ms 39800 KB Output isn't correct
40 Incorrect 640 ms 39928 KB Output isn't correct
41 Correct 190 ms 40312 KB Output is correct
42 Incorrect 692 ms 40056 KB Output isn't correct