oj.uz

Submission #1109636

# Submission time Handle Problem Language Result Execution time Memory
1109636 2024-11-07T08:17:24 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 59 ms 14868 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }
const int mod = 1e9 +7, sze = 1e5 +10, inf = INT_MAX, LG = 20;
int dp[sze];
void fast(){
    int n,q;
    cin>>n>>q;
    int mx = 0;

    set<pair<int,int>> var;
    for(int i=1;i<=n;i++){
        int p;cin>>p;
        mx=max(mx,p);
        var.ins({p,p});
    }
    for(int i=1;i<sze;i++){
        dp[i]=inf;
        while(!var.empty()){
            auto it = *var.begin();
            if( it.first + it.second<=i){
                // cout<<i<<" "<<it.first<<" "<<it.second<<endl;
                if(it.first + it.second < sze){
                    var.ins({it.first + it.second,it.second});
                }
                var.erase(var.begin());
            }
            else{
                break;
            }
        }
        if(i<mx){
            dp[i]=1;
        }
        else{
            // cout<<i<<" "<<var.size()<<endl;
            if(!var.empty()){

                auto it = *var.begin();
                // cout<<i<<" "<<it.first<<endl;
                dp[i]= dp[it.first] +1;
            }
        }
    }

 
    while(q--){
        int v;
        cin>>v;
        if(dp[v]>=inf){
            cout<<"oo"<<endl;
        }
        else{
            cout<<dp[v]<<endl;
        }
    }
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 8 ms 1140 KB Output is correct
3 Correct 5 ms 1104 KB Output is correct
4 Correct 3 ms 1104 KB Output is correct
5 Correct 3 ms 1104 KB Output is correct
6 Correct 2 ms 1104 KB Output is correct
7 Correct 5 ms 1212 KB Output is correct
8 Correct 6 ms 1104 KB Output is correct
9 Correct 10 ms 1104 KB Output is correct
10 Correct 14 ms 1104 KB Output is correct
11 Correct 10 ms 1104 KB Output is correct
12 Correct 2 ms 1104 KB Output is correct
13 Correct 26 ms 1104 KB Output is correct
14 Correct 25 ms 1104 KB Output is correct
15 Correct 10 ms 1104 KB Output is correct
16 Correct 8 ms 1060 KB Output is correct
17 Correct 6 ms 1112 KB Output is correct
18 Correct 3 ms 1104 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 3664 KB Execution killed with signal 11
2 Runtime error 35 ms 13648 KB Execution killed with signal 11
3 Runtime error 51 ms 11012 KB Execution killed with signal 11
4 Runtime error 8 ms 2384 KB Execution killed with signal 11
5 Runtime error 28 ms 8480 KB Execution killed with signal 11
6 Runtime error 6 ms 2140 KB Execution killed with signal 11
7 Runtime error 10 ms 3676 KB Execution killed with signal 11
8 Runtime error 7 ms 2140 KB Execution killed with signal 11
9 Runtime error 36 ms 11092 KB Execution killed with signal 11
10 Runtime error 45 ms 10836 KB Execution killed with signal 11
11 Runtime error 31 ms 7260 KB Execution killed with signal 11
12 Runtime error 11 ms 2396 KB Execution killed with signal 11
13 Runtime error 5 ms 2396 KB Execution killed with signal 11
14 Runtime error 6 ms 2396 KB Execution killed with signal 11
15 Runtime error 29 ms 7260 KB Execution killed with signal 11
16 Runtime error 34 ms 13648 KB Execution killed with signal 11
17 Runtime error 21 ms 2384 KB Execution killed with signal 11
18 Runtime error 59 ms 14664 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 8520 KB Execution killed with signal 11
2 Runtime error 36 ms 8716 KB Execution killed with signal 11
3 Runtime error 36 ms 8288 KB Execution killed with signal 11
4 Runtime error 11 ms 2384 KB Execution killed with signal 11
5 Runtime error 37 ms 14580 KB Execution killed with signal 11
6 Runtime error 18 ms 3152 KB Execution killed with signal 11
7 Runtime error 43 ms 14868 KB Execution killed with signal 11
8 Runtime error 32 ms 8392 KB Execution killed with signal 11
9 Runtime error 36 ms 8440 KB Execution killed with signal 11
10 Runtime error 12 ms 2896 KB Execution killed with signal 11
11 Runtime error 10 ms 2640 KB Execution killed with signal 11
12 Runtime error 17 ms 2908 KB Execution killed with signal 11
13 Runtime error 30 ms 5968 KB Execution killed with signal 11
14 Runtime error 17 ms 1968 KB Execution killed with signal 11
15 Runtime error 18 ms 2896 KB Execution killed with signal 11
16 Runtime error 20 ms 3004 KB Execution killed with signal 11
17 Runtime error 25 ms 7884 KB Execution killed with signal 11
18 Runtime error 41 ms 8848 KB Execution killed with signal 11
19 Runtime error 6 ms 2640 KB Execution killed with signal 11
20 Runtime error 39 ms 8392 KB Execution killed with signal 11
21 Runtime error 19 ms 2128 KB Execution killed with signal 11
22 Runtime error 52 ms 14676 KB Execution killed with signal 11
23 Runtime error 12 ms 5976 KB Execution killed with signal 11
24 Runtime error 4 ms 2140 KB Execution killed with signal 11
25 Runtime error 13 ms 2368 KB Execution killed with signal 11
26 Runtime error 10 ms 2396 KB Execution killed with signal 11
27 Runtime error 58 ms 14852 KB Execution killed with signal 11
28 Runtime error 6 ms 2140 KB Execution killed with signal 11
29 Runtime error 47 ms 14824 KB Execution killed with signal 11
30 Runtime error 35 ms 11100 KB Execution killed with signal 11
31 Runtime error 7 ms 2652 KB Execution killed with signal 11
32 Runtime error 7 ms 2396 KB Execution killed with signal 11
33 Runtime error 4 ms 2140 KB Execution killed with signal 11
34 Runtime error 42 ms 14680 KB Execution killed with signal 11
35 Runtime error 5 ms 2396 KB Execution killed with signal 11
36 Runtime error 47 ms 13380 KB Execution killed with signal 11
37 Runtime error 38 ms 14676 KB Execution killed with signal 11
38 Runtime error 21 ms 3164 KB Execution killed with signal 11
39 Runtime error 4 ms 2268 KB Execution killed with signal 11
40 Runtime error 17 ms 3168 KB Execution killed with signal 11
41 Runtime error 49 ms 14752 KB Execution killed with signal 11
42 Runtime error 18 ms 2396 KB Execution killed with signal 11