Submission #1358810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1358810		charlesti	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	69.52 / 100	1101 ms	252220 KiB

brunhilda

// TLE cuz tmp pq

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast, unroll-loops")
#define pii pair<int, int>
#define f first
#define s second
using namespace std;

struct cha{
    int opr, id, num;
    bool operator < (const cha& o) const{
        return opr > o.opr;
    }
};
int dp[10000069];
int head[10000069];
int nxt[100069];
int st[100069];
int a[100069];
int qu[100069];
cha tmp[100069];
int mx = 0;


signed main(){

    cin.tie(0); ios::sync_with_stdio(0);
    int m, q; cin >> m >> q;
    for(int i=1; i<=m; i++){
        cin >> a[i];
    }

    for(int i=1; i<=q; i++){
        cin >> qu[i];
        mx = max(mx, qu[i]);
    }

    for(int i=1; i<=m; i++){
        if(a[i] <= mx){
            nxt[i] = head[a[i]];
            head[a[i]] = i;
        }
    }

    priority_queue<cha> pq;
    dp[0] = 0;
    for(int i=1; i<=m; i++){
        st[i] = 0;
        pq.push({0, i, 0});
    }

    for(int i=1; i<=mx; i++){

        // priority_queue<cha> tmp;
        int sz = 0;
        while(!pq.empty()){
            auto[opr, id, num] = pq.top();
            int gg = 0;
            if(i % a[id] == 0) gg = 1;

            if(st[id] != num) {
                // cout << num << "POP\n";
                pq.pop();
            }
            else if(gg){
                tmp[sz++] = pq.top(); pq.pop();
                // tmp.push({opr, id, num}); pq.pop();
                // cout << i << "same\n";
            }
            else{
                break;
            }
        }

        if(pq.empty()) {
            dp[i] = -1;
            // if(i==4 && !tmp.empty()) cout << tmp.top().num << "S\n";
            // while(!tmp.empty()){
            //     pq.push(tmp.top()); tmp.pop();
            // }
            for(int k=0; k<sz; k++) pq.push(tmp[k]);
        } else {
            // if(i==5) cout << pq.top().opr << ' ' << pq.top().num << "Five\n";
            dp[i] = pq.top().opr + 1;
            // while(!tmp.empty()){
            //     pq.push(tmp.top()); tmp.pop();
            // }
            for(int k=0; k<sz; k++) pq.push(tmp[k]);
        }

        int cur = head[i];
        while(cur != 0){
            int ID = nxt[cur];

            st[cur] = i;
            if(dp[i] != -1) {
                pq.push({dp[i], cur, i});
                // cout << i << ' ' << dp[i] << "PU\n";
            }

            int mul = i + a[cur];
            if(mul <= mx){
                nxt[cur] = head[mul];
                head[mul] = cur;
            }

            cur = ID;
        }
        // cout << i << ' ' << pq.top().num << ' ' << pq.top().opr << "TOP\n";
    }

    // for(int i=1; i<=10; i++) cout << i << ' ' << dp[i] << "A\n";

    for(int i=1; i<=q; i++){
        if(dp[qu[i]] == -1) cout << "oo\n";
        else cout << dp[qu[i]] << '\n';
    }

    return 0;
}

/*
2 2
2 3
5
6

*/

Compilation message (stderr)

brunhilda.cpp:4:43: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("Ofast, unroll-loops")
      |                                           ^
brunhilda.cpp:12:36: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   12 |     bool operator < (const cha& o) const{
      |                                    ^~~~~
brunhilda.cpp:26:13: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   26 | signed main(){
      |             ^

• Subtask 1: 20 / 20
• Subtask 2: 16.6667 / 20
• Subtask 3: 32.8571 / 60