Submission #1358821

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

brunhilda

// TLE cuz tmp pq

#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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; scanf("%d %d", &m, &q);
    for(int i=1; i<=m; i++){
        scanf("%d", &a[i]);
    }

    for(int i=1; i<=q; i++){
//        cin >> qu[i];
        scanf("%d", &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) printf("oo\n");
        else printf("%d\n", dp[qu[i]]);
    }

    return 0;
}

/*
2 2
2 3
5
6

*/

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:30:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     int m, q; scanf("%d %d", &m, &q);
      |               ~~~~~^~~~~~~~~~~~~~~~~
brunhilda.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
brunhilda.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d", &qu[i]);
      |         ~~~~~^~~~~~~~~~~~~~

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