oj.uz

Submission #1109614

# Submission time Handle Problem Language Result Execution time Memory
1109614 2024-11-07T07:15:07 Z 0pt1mus23 Brunhilda’s Birthday (BOI13_brunhilda) C++14
8.09524 / 100
 112 ms 88248 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 = 1e7 +10, inf = INT_MAX, LG = 20;
int dp[sze];
void fast(){
    int n,q;
    cin>>n>>q;
    multiset<int> ans; 
    int mx = 0;
    vector<pair<int,int>> ev;
    for(int i=1;i<=n;i++){
        int p;cin>>p;
        // event[p].pb(p);
        ev.pb({p,p});
        mx=max(mx,p);
    }
    vector<int> primus;
    int j=0;
    pair<int,int> beg;
    for(int i =1;i<sze;i++){
        dp[i]=inf;
        primus.clear();
        while(j<ev.size()){
            beg = ev[j];
            if(beg.first != i){
                break;
            }
            j++;
            primus.pb(beg.second);
            if(i != beg.second){
                ans.erase(ans.find(dp[i - beg.second]));
            }
        }
        if( i < mx ){
            dp[i]=1;
        }
        else if(!ans.empty()){
            dp[i]= (*ans.begin())+1;
        }
        if(dp[i]<inf){
            for(auto v:primus){
                ans.ins(dp[i]);
                ev.pb({i + v,v});
            }
        }
    }
 
 
    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;
}

Compilation message

brunhilda.cpp: In function 'void fast()':
brunhilda.cpp:30:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         while(j<ev.size()){
      |               ~^~~~~~~~~~

Subtask #1
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 78532 KB Output isn't correct
2 Incorrect 45 ms 78516 KB Output isn't correct
3 Incorrect 45 ms 78676 KB Output isn't correct
4 Incorrect 46 ms 78664 KB Output isn't correct
5 Incorrect 45 ms 78676 KB Output isn't correct
6 Incorrect 53 ms 78520 KB Output isn't correct
7 Incorrect 47 ms 78672 KB Output isn't correct
8 Incorrect 49 ms 78664 KB Output isn't correct
9 Incorrect 54 ms 78644 KB Output isn't correct
10 Incorrect 52 ms 78664 KB Output isn't correct
11 Incorrect 51 ms 78672 KB Output isn't correct
12 Correct 51 ms 78676 KB Output is correct
13 Correct 50 ms 78664 KB Output is correct
14 Correct 52 ms 78624 KB Output is correct
15 Incorrect 54 ms 78516 KB Output isn't correct
16 Incorrect 50 ms 78672 KB Output isn't correct
17 Incorrect 57 ms 78692 KB Output isn't correct
18 Incorrect 51 ms 78664 KB Output isn't correct

Subtask #2
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 79572 KB Output isn't correct
2 Correct 64 ms 86920 KB Output is correct
3 Incorrect 68 ms 85908 KB Output isn't correct
4 Incorrect 52 ms 78920 KB Output isn't correct
5 Incorrect 67 ms 83136 KB Output isn't correct
6 Incorrect 50 ms 78688 KB Output isn't correct
7 Incorrect 52 ms 79468 KB Output isn't correct
8 Incorrect 49 ms 78664 KB Output isn't correct
9 Correct 71 ms 85944 KB Output is correct
10 Incorrect 68 ms 86116 KB Output isn't correct
11 Incorrect 60 ms 82624 KB Output isn't correct
12 Incorrect 49 ms 78920 KB Output isn't correct
13 Incorrect 49 ms 78940 KB Output isn't correct
14 Incorrect 51 ms 78920 KB Output isn't correct
15 Incorrect 60 ms 82624 KB Output isn't correct
16 Correct 65 ms 86972 KB Output is correct
17 Incorrect 56 ms 78732 KB Output isn't correct
18 Incorrect 74 ms 87460 KB Output isn't correct

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 83136 KB Output isn't correct
2 Incorrect 76 ms 83148 KB Output isn't correct
3 Incorrect 71 ms 83464 KB Output isn't correct
4 Incorrect 78 ms 79692 KB Output isn't correct
5 Incorrect 90 ms 88248 KB Output isn't correct
6 Incorrect 69 ms 80076 KB Output isn't correct
7 Incorrect 81 ms 87960 KB Output isn't correct
8 Incorrect 70 ms 83196 KB Output isn't correct
9 Incorrect 76 ms 83136 KB Output isn't correct
10 Incorrect 62 ms 79156 KB Output isn't correct
11 Incorrect 76 ms 79224 KB Output isn't correct
12 Incorrect 60 ms 79280 KB Output isn't correct
13 Incorrect 68 ms 81868 KB Output isn't correct
14 Incorrect 66 ms 79440 KB Output isn't correct
15 Incorrect 58 ms 79176 KB Output isn't correct
16 Incorrect 56 ms 79276 KB Output isn't correct
17 Incorrect 67 ms 82912 KB Output isn't correct
18 Incorrect 78 ms 83136 KB Output isn't correct
19 Incorrect 55 ms 78964 KB Output isn't correct
20 Incorrect 72 ms 83432 KB Output isn't correct
21 Incorrect 66 ms 79688 KB Output isn't correct
22 Incorrect 112 ms 88140 KB Output isn't correct
23 Incorrect 77 ms 81664 KB Output isn't correct
24 Incorrect 76 ms 78868 KB Output isn't correct
25 Incorrect 76 ms 79764 KB Output isn't correct
26 Incorrect 72 ms 79564 KB Output isn't correct
27 Incorrect 88 ms 87736 KB Output isn't correct
28 Incorrect 60 ms 78888 KB Output isn't correct
29 Incorrect 91 ms 88244 KB Output isn't correct
30 Incorrect 99 ms 86936 KB Output isn't correct
31 Incorrect 71 ms 79944 KB Output isn't correct
32 Incorrect 70 ms 79536 KB Output isn't correct
33 Incorrect 67 ms 78868 KB Output isn't correct
34 Incorrect 86 ms 87892 KB Output isn't correct
35 Incorrect 62 ms 78924 KB Output isn't correct
36 Incorrect 103 ms 87584 KB Output isn't correct
37 Incorrect 100 ms 88136 KB Output isn't correct
38 Incorrect 69 ms 79972 KB Output isn't correct
39 Incorrect 78 ms 79032 KB Output isn't correct
40 Incorrect 71 ms 80028 KB Output isn't correct
41 Correct 87 ms 87952 KB Output is correct
42 Incorrect 72 ms 79688 KB Output isn't correct