제출 #1358832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358832		charlesti	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	28.10 / 100	1101 ms	252528 KiB

brunhilda

// TLE cuz tmp pq

#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#include <ext/pb_ds/priority_queue.hpp>
//using namespace __gnu_pbds;
#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 mark[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;
    // __gnu_pbds::priority_queue<cha, less<cha>, pairing_heap_tag> 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++){

        int cur = head[i];
        while(cur != 0){
            mark[cur] = 1;
            cur = nxt[cur];
        }

        while(!pq.empty()){
            cha t = pq.top();
            int id = t.id;
            int num = t.num;

            if(st[id] != num){
                pq.pop();
            }
            else if(mark[id]){
                pq.pop();
            }
            else{
                break;
            }
        }

        if(pq.empty()) {
            dp[i] = -1;
        } else {
            dp[i] = pq.top().opr + 1;
        }

        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;
        }

        cur = head[i];
        while(cur != 0){
            mark[cur] = 0;
            cur = nxt[cur];
        }
        // 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

*/

컴파일 시 표준 에러 (stderr) 메시지

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

• 서브태스크 1: 7.7778 / 20
• 서브태스크 2: 8.8889 / 20
• 서브태스크 3: 11.4286 / 60