oj.uz

Submission #1109608

# Submission time Handle Problem Language Result Execution time Memory
1109608 2024-11-07T07:02:19 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 59 ms 19852 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];
vector<pair<int,int>> event[sze];
void fast(){
    for(int i=1;i<sze;i++){
        dp[i]=inf;
    }
    int n,q;
    cin>>n>>q;
    multiset<int> ans; 
    int mx = 0;
    for(int i=1;i<=n;i++){
        int p;cin>>p;
        event[p].pb({p,p});
        mx=max(mx,p);
    }
    for(int i =1;i<sze;i++){
        for(auto v:event[i]){
            if(ans.find(dp[v.first]) !=ans.end() ){
                ans.erase(ans.find(dp[v.first]));
            }
        }
        if( ans.empty() ){
            if(i < mx){
                dp[i]=1;
            }
        }
        else{
            dp[i]= (*ans.begin())+1;
        }
        if(dp[i]<inf){
            for(auto v:event[i]){
                ans.ins(dp[i]);
                if(i + v.second < sze){
                    event[i + v.second].pb({i,v.second});
                }
            }
        }
    }
 
 
    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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3408 KB Output isn't correct
2 Incorrect 18 ms 6256 KB Output isn't correct
3 Incorrect 9 ms 5724 KB Output isn't correct
4 Incorrect 19 ms 3832 KB Output isn't correct
5 Incorrect 6 ms 4432 KB Output isn't correct
6 Incorrect 4 ms 3408 KB Output isn't correct
7 Incorrect 15 ms 5712 KB Output isn't correct
8 Incorrect 10 ms 6480 KB Output isn't correct
9 Incorrect 17 ms 7084 KB Output isn't correct
10 Incorrect 23 ms 7372 KB Output isn't correct
11 Incorrect 17 ms 6480 KB Output isn't correct
12 Incorrect 3 ms 3664 KB Output isn't correct
13 Incorrect 39 ms 9288 KB Output isn't correct
14 Incorrect 53 ms 9288 KB Output isn't correct
15 Incorrect 15 ms 6224 KB Output isn't correct
16 Incorrect 18 ms 6240 KB Output isn't correct
17 Incorrect 23 ms 4432 KB Output isn't correct
18 Incorrect 19 ms 3664 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 6992 KB Execution killed with signal 11
2 Runtime error 7 ms 6932 KB Execution killed with signal 11
3 Runtime error 11 ms 7504 KB Execution killed with signal 11
4 Runtime error 18 ms 10076 KB Execution killed with signal 11
5 Runtime error 8 ms 7248 KB Execution killed with signal 11
6 Runtime error 21 ms 11088 KB Execution killed with signal 11
7 Runtime error 7 ms 6992 KB Execution killed with signal 11
8 Incorrect 10 ms 4688 KB Output isn't correct
9 Runtime error 8 ms 7248 KB Execution killed with signal 11
10 Runtime error 8 ms 7248 KB Execution killed with signal 11
11 Runtime error 9 ms 7248 KB Execution killed with signal 11
12 Runtime error 33 ms 13652 KB Execution killed with signal 11
13 Runtime error 6 ms 6736 KB Execution killed with signal 11
14 Runtime error 18 ms 10064 KB Execution killed with signal 11
15 Runtime error 7 ms 7248 KB Execution killed with signal 11
16 Runtime error 7 ms 6992 KB Execution killed with signal 11
17 Runtime error 52 ms 18768 KB Execution killed with signal 11
18 Runtime error 8 ms 7248 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 7248 KB Execution killed with signal 11
2 Runtime error 10 ms 7516 KB Execution killed with signal 11
3 Runtime error 11 ms 7504 KB Execution killed with signal 11
4 Runtime error 43 ms 14328 KB Execution killed with signal 11
5 Runtime error 8 ms 6992 KB Execution killed with signal 11
6 Runtime error 8 ms 7248 KB Execution killed with signal 11
7 Runtime error 7 ms 7188 KB Execution killed with signal 11
8 Runtime error 7 ms 7248 KB Execution killed with signal 11
9 Runtime error 8 ms 7248 KB Execution killed with signal 11
10 Runtime error 30 ms 13648 KB Execution killed with signal 11
11 Runtime error 24 ms 11892 KB Execution killed with signal 11
12 Runtime error 48 ms 16968 KB Execution killed with signal 11
13 Runtime error 8 ms 7504 KB Execution killed with signal 11
14 Runtime error 33 ms 15360 KB Execution killed with signal 11
15 Runtime error 49 ms 18776 KB Execution killed with signal 11
16 Runtime error 59 ms 19852 KB Execution killed with signal 11
17 Runtime error 8 ms 7248 KB Execution killed with signal 11
18 Runtime error 8 ms 7504 KB Execution killed with signal 11
19 Runtime error 7 ms 6992 KB Execution killed with signal 11
20 Runtime error 9 ms 7520 KB Execution killed with signal 11
21 Runtime error 42 ms 16640 KB Execution killed with signal 11
22 Runtime error 9 ms 7252 KB Execution killed with signal 11
23 Runtime error 9 ms 6992 KB Execution killed with signal 11
24 Runtime error 11 ms 8016 KB Execution killed with signal 11
25 Runtime error 35 ms 14152 KB Execution killed with signal 11
26 Runtime error 36 ms 14400 KB Execution killed with signal 11
27 Runtime error 9 ms 7672 KB Execution killed with signal 11
28 Runtime error 6 ms 6992 KB Execution killed with signal 11
29 Runtime error 8 ms 7248 KB Execution killed with signal 11
30 Runtime error 8 ms 7368 KB Execution killed with signal 11
31 Runtime error 6 ms 6992 KB Execution killed with signal 11
32 Runtime error 21 ms 10576 KB Execution killed with signal 11
33 Runtime error 6 ms 6736 KB Execution killed with signal 11
34 Runtime error 8 ms 7268 KB Execution killed with signal 11
35 Runtime error 8 ms 6992 KB Execution killed with signal 11
36 Runtime error 8 ms 7248 KB Execution killed with signal 11
37 Runtime error 7 ms 7064 KB Execution killed with signal 11
38 Runtime error 8 ms 7420 KB Execution killed with signal 11
39 Runtime error 6 ms 6848 KB Execution killed with signal 11
40 Runtime error 7 ms 7248 KB Execution killed with signal 11
41 Runtime error 7 ms 7260 KB Execution killed with signal 11
42 Runtime error 52 ms 19468 KB Execution killed with signal 11