TopCoder

User's AC Ratio

100.0% (38/38)

Submission's AC Ratio

93.6% (117/125)

Tags

Description

2222 年 5 月,大廠牌電子機械製造商 ARGUS 發佈了能夠實現虛擬實境的機器 NerveGear,人們可以通過 NerveGear 進行完全潛行以進入虛擬世界。不久,全球首款虛擬實境大型多人線上角色扮演遊戲《刀劍神域》在經過大約一千人參加的封閉測試後正式發佈,首次共限量發售一萬份。《刀劍神域》於 2222 年 11 月 6 日下午 1 時正式開始營運。

明奕身為《刀劍神域》的粉絲,他當然不只是搶到了封閉測試的資格,也拿到了限量的正式版參與名額,並在遊戲營運當天馬上登入了遊戲。而你,身為明奕的朋友,雖然沒有搶到正式版名額,但也非常關注《刀劍神域》的消息。在遊戲開始營運後沒多久,還在蒐集資訊的你便發現了遊戲設計者茅場晶彥的陰謀──《刀劍神域》將會在時間 $T$ 之後關閉登出指令,並成為一個不破關就無法登出、在遊戲內死去也會在現實中死去的死亡遊戲!

但這時你回想起來,明奕曾經說過他只打算在第一天把遊戲角色升級到 $L$ 等就先退出遊戲去趕他的計安作業,所以只要明奕成功在時間 $T$ 以前練到 $L$ 等,他就可以平安無事的提早度過這個風波。在你確認過手邊整理過的遊戲資料後,你發現這個遊戲目前有 $N$ 個任務可以接,每個任務有兩個參數 $l_i, t_i$,代表可以接下這個任務的最低等級和所需花費的時間,並且在一開始時,所有玩家的等級都是 $1$ 等,在《刀劍神域》裡升到 $L$ 等之前,每一等都只需要完成 $K$ 個任務就可以升一等。

你知道明奕一定會用最少的時間升到 $L$ 等,但你一時又聯絡不上專心練等的明奕,因此你只好先計算出他升到 $L$ 等的最少時間,並根據他能不能在時間 $T$ 以前升到 $L$ 等來採取下一步的動作,快撰寫一支程式來完成這件事情吧!

以下為提供的解法,但是卻得到 WA,請在 edit distance $8$ 以內將該程式碼修改正確:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N, L, K, T;
    string s = "Impossible";
    cin >> N >> L >> K >> T;

    vector<pair<int, int>> arr(N);
    for (auto &[l, t] : arr)
        cin >> l >> t;

    sort(arr.begin(), arr.end(), [](pair<int, int> a, pair<int, int> b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    });

    auto quited = [&](string &verdict) {
        int ans = 0, lv = 1;

        priority_queue<int, vector<int>, greater<int>> min_heap;

        for (int pt = 0, exp = 0; lv < L;) {
            while (pt < N && arr[pt].first <= lv)
                min_heap.push(arr[pt++].second);
            if (min_heap.empty()) return verdict;

            ans += min_heap.top();
            min_heap.pop();

            exp += 1;
            if (exp == K) exp = 0, lv += 1;
        }

        if (ans > T)
            verdict = "Time Limit Exceeded";
        else {
            cout << ans << "\n";
            exit(0);
        }

        return verdict;
    };

    cout << quited(s) << "\n";
}

Input Format

輸入首行有四個整數 $N, L, K, T$,代表任務的數量、明奕的目標等級、升一等所需完成的任務數量和《刀劍神域》關閉登出指令的時間點。

接下來 $N$ 行,第 $i$ 行兩個整數 $l_i, t_i$,代表接下第 $i$ 個任務的最低等級限制、以及完成第 $i$ 個任務所需花費的時間。

  • $1 \leq N \leq 10^ 5$
  • $1 \leq L \leq 10^ 4$
  • $1 \leq K \leq 10$
  • $1 \leq T \leq 10^ 9$
  • $1 \leq l_i, t_i \leq 10^ 4$

Output Format

如果明奕其實不能靠當前這 $N$ 個任務升到 $L$ 等,輸出 "Impossible"(含引號)於一行,否則,假設明奕升到 $L$ 等的最少時間為 $x$,若 $x > T$,表示明奕已經來不及退出遊戲了,輸出 "Time Limit Exceeded"(含引號)於一行;反之輸出 $x$ 於一行。

Sample Input 1

3 3 1 10
1 3
1 8
2 7

Sample Output 1

10

Sample Input 2

5 3 2 10
1 1
1 3
1 3
2 2
3 1

Sample Output 2

9

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~8 無特別限制。 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2