669 . 排隊結帳

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

28.9% (13/45)

Tags

apcsc apcsc-ds

Description

在一個商場有 N 條排隊動線。一開始所有動線都是空的，之後依序發生了 M 個事件，事件可能是以下三者之一，記錄如下：

  • 紀錄 ADD i x 表示一個客人 x 加入了第 i 條排隊隊伍最後方。
  • 紀錄 LEAVE i 表示第 i 條排隊隊伍最前方客人完成結帳離開隊伍。
  • 紀錄 JOIN i j 表示第 i 條動線臨時關閉，所有第 i 條動線的客人依序加入第 j 條動線尾端。

Input Format

輸入第一行是兩個數字 N,M，分別表示排隊動線數量和事件數。
接著有 M 條指令，每條指令一定是 ADD i x，LEAVE i，JOIN i j 三者之一。

輸入保證 1≤N≤100，1≤M≤2×105，1≤i,j≤N，1≤x≤106，並保證沒有重複編號的客人，以及不會有關閉隊伍 i 後客人隨即加入隊伍 i 的情況。

Output Format

輸入保證 ADD 和 JOIN 合法。
對於 LEAVE i 操作，如果第 i 條隊伍是空的，請輸出 queue i is empty! 並忽略操作。其中 i 是指隊伍編號，例如第 3 條隊伍是空的則輸出 queue 3 is empty!
在所有操作結束後，依序輸出 n 行，第 i 行輸出 queue i:，隨後輸出若干個空白分隔的整數表示隊伍從頭到尾排隊的人編號，如果隊伍是空的請在其後輸出 empty。例如若第 1 條動線是空的，輸出 queue 1: empty，第 2 條動線依序是 1,2 號排隊則輸出 queue 2: 1 2。請見範例。

Sample Input 1

3 10
ADD 1 1
ADD 1 2
ADD 2 3
ADD 2 4
ADD 3 5
LEAVE 3
LEAVE 3
ADD 3 6
JOIN 2 3
JOIN 1 2

Sample Output 1

queue 3 is empty!
queue 1: empty
queue 2: 1 2
queue 3: 6 3 4

Hints

Problem Source

Sprout OJ

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~15 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2
15 2000 524288 65536 2
Submit
Back to Top