제출 #1358796

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

brunhilda

// TLE

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

int dp[10000069];
int head[10000069];
int nxt[100069];
int st[100069];
int a[100069];
int qu[100069];
int mx = 0;

struct cha{
    int opr, id, num;
    bool operator < (const cha& o) const{
        return opr > o.opr;
    }
};

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;
        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.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();
            }
        } 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();
            }
        }

        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

*/

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

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

• 서브태스크 1: 20 / 20
• 서브태스크 2: 17.7778 / 20
• 서브태스크 3: 34.2857 / 60