655 . 大鍋飯排隊問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

30.8% (8/26)

Tags

apcsc apcsc-ds

Description

「大鍋飯」中式餐館是北京城時下最時髦的用餐地點！每到中午用餐時間，「大鍋飯」飯館總是大排長龍，熙熙攘攘。現在，他們想要寫一支程式來處理 T 天的排隊資料。已知第 i 天有 Ni 個旅行團來到，其中的第 j 個旅行團有 cj 個人，也知道他們的編號是 xj,1,xj,2,…,xj,cj。而又會有 Qi 個「事件」發生，可能是下列兩個的其中之一：

  • 編號為 x 的人進入了餐館
  • 餐館放一個人進來餐館內，目前在隊伍最前面的人離隊，並且輸出這個人是誰

但是，因為「大鍋飯」中式餐館實在太好吃了，午休時間又很短，導致人們在這裡特別喜歡插隊：如果一個人進來看到隊伍裡面已經有和他同一個旅行團的人在排隊的話，他會毫不猶豫地排到他們的後面。而且，每一天結束之後，不管隊伍還有沒有人，所有人都會離開商店。請注意，不同隊伍的人不會出現相同編號，但因為北京城流行分享編號，所以可能隊伍裡面同時會有兩個人的編號是相同的，這是被允許的，請將他們兩個人處理為兩個不同而編號相同的人。

請寫一支支援以上兩個操作的程式吧！

Input Format

第一行有一個數字 T(1≤T≤105)，代表有幾天。接下來會有 T 筆測試資料，每一筆的第一行都會有兩個數字 N 和 Q(1≤N,Q≤105)。接下來的 N 行每一行都會有若干個數字，其中第一個是 cj(1≤cj≤105)，接下來有 cj 個數字 xj,1,xj,2,…,xj,cj(1≤xi,j≤106)。接下來是 Q 行，可能是下列的其中兩個中的之一：

  • 1 x 代表編號為 x 的人加入了隊伍。
  • 2 代表隊伍最前面的人離隊，請輸出那個人的編號。如果沒有人，請輸出 −1。

此外，還保證 ∑N,∑Q,∑cj≤105，且所有入隊伍的人都是之前出現過的團員，且一個編號最多只會屬於一個旅行團。

Output Format

對於每一個詢問，請於一行輸出對應的答案。

Sample Input 1

1
2 13
3 101 102 103
3 201 202 203
1 101
1 201
1 102
1 202
1 103
1 203
2
2
2
2
2
2
2

Sample Output 1

101
102
103
201
202
203
-1

Hints

Problem Source

修改自 UVa 540 - Team Queue

Subtasks

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

Testdata and Limits

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