TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

81.2% (13/16)

Submission's AC Ratio

16.5% (30/182)

Description

中國有許多獨特的傳統,如鼎鼎大名的「中國洗衣問題」就曾經讓許多人百思不得其解。除了中國洗衣問題以外,「中國隊列」也是一個印證中國人超群智慧的文化。

「中國隊列」可以描述如下:假設今天有$N$個中國人,分別編號為1到N,將這些人稱為$p_1, p_2,\cdots, p_{N}$。若這些中國人要排成一個隊列,則他們會按照編號$a_1,a_2,\cdots ,a_{N}$的順序一個一個進入隊列:$p_{a_1}$會先進入隊列,接下來$p_{a_i}$進入時,他會找$p_{a_1},p_{a_2},\cdots ,p_{a_{i-1}}$中任一個人,排在他的前或後方。這種隊列我們稱之為「中國隊列」。
中國隊列並不是一成不變的。在形成隊列過程中可能會發生人群的「重組」現象:對於已經在隊列裡的一群人,他們互相討論好之後,可以一起按照原先的順序移動到另一個也在隊列中的人的前面。「重組」現象是中國隊列的精髓所在,必須要有強大的合作精神才有可能做到大規模的重組。
例如,一開始隊列由前到後依序是$p_4, p_9, p_3, p_1, p_5, p_8$,若$p_5$前面、$p_3$後面的所有人(也就是$p_1, p_3, p_5$三人)討論好要移動到$p_4$前面的話,重組後的隊列就會變成$p_3, p_1, p_5, p_4, p_9, p_8$。

某日一群中國人準備要排成中國隊列領取訂購的商品。很恰好地,他們買的商品都是某種食物,並且每個人都只買了一個。
這個店家知道中國文化的精妙之處,因此決定使用以下的策略發放商品:他們每生產一批$B$個商品之後,就會在當前的隊列中選定一個人$A$,並且從$A$開始一個一個往隊列的前方或後方發(往排在最前面的人的方向稱為前方),一直到$B$個商品都發放完畢為止。拿到商品的人就會直接離開隊列。如果發到隊列的末端還沒把$B$個商品發完的話,剩餘的那些就視為作廢。為了不造成混亂,店家會在完成這批商品的發放之後才允許其他人進入隊列。

給定一個中國隊列形成、重組與商品發放的過程,請你求出所有中國人拿到商品的順序,以及這個店家總共作廢了幾個商品。

Input Format

第一行有一個正整數$T$,代表測資筆數。
接下來每一筆測資中,第一行有三個非負整數$N,M,a_1$,分別代表要進入隊列的中國人的數量、總共發生了幾個事件與第一個進入隊列的中國人編號。(進入隊列、重組、發放商品都稱為事件,但是第一個進入隊列不算一次事件。)

接下來有$M$行,每行有四個正整數K, A, B, C,其中$K\leq 3$且$A,B,C\leq N$。
如果K=1,則$C\leq 2$,代表$p_A$進入隊列。如果C=1,代表他排在$p_B$的前面;如果C=2,代表他排在$p_B$的後面。保證$p_A$未曾進入隊列,且$p_B$正在隊列當中。
如果K=2,代表一次重組,排在$p_A$後面且在$p_B$前面的所有人,都移動到$p_C$前面。保證$p_A, p_B, p_C$都正在隊列當中,並且$A=B$或者$p_A$排在$p_B$的前面,且$p_C$不在$p_A$和$p_B$之間。
如果K=3,則$B \geq 1, C\leq 2$,代表店家從$p_A$開始發放B個商品。如果C=1,代表往前方發放商品;如果C=2,代表往後方發放商品。保證$p_A$正在隊列當中,且除了最後一次發放商品以外,發放完商品的時候必定還有人在隊列中。

保證整個過程結束後,所有中國人都有拿到商品。

Output Format

對於每筆測資,請輸出$N+1$行,每行有一個非負整數。
第一行請輸出店家總共作廢了幾個商品。接下來$N$行請由最先到最後的順序輸出拿到商品的中國人編號。

Sample Input

1
6 9 5
1 3 5 2
1 6 5 2
1 2 3 1
2 2 2 6
3 3 5 2
1 4 2 2
1 1 4 1
3 1 5 1
3 6 2 1

Sample Output

6
3
1
2
5
6
4

Hints

本題共有五組測試資料。每組可有多個輸入檔案,全部答對該組才得分。

第一組27分,$T\leq 2, a_1\leq N<M\leq 10^ 4$
第二組22分,$T=1, a_1\leq N<M\leq 10^ 5$
第三組17分,$T\leq 3, a_1\leq N<M\leq 10^ 6$,不會有重組,且無論是進入隊列或發放商品都必定發生在隊伍的最前方或最後方
第四組34分,$T\leq 3, a_1\leq N<M\leq 2\times 10^ 6$

注意事項:
使用C++作答的同學,請在程式碼開頭加上#include<cstdio>,並利用scanf讀入資料、用printf輸出資料。使用cin / cout讀入/輸出資料可能會因為效率太差以致於程式執行時間超過限制。
scanf 常用的讀入方式如下:
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。
printf 常用的輸出方式如下:
printf("%d\n",x); 輸出一行包含一個int 型態變數x。
printf("%lld\n",y); 輸出一行包含一個long long 型態變數y。
printf("%u\n",x); 輸出一行包含一個unsigned int 型態變數x。
printf("%llu\n",y); 輸出一行包含一個unsigned long long 型態變數y。

Problem Source

Problem Set / Description by Yihda Yol
建國中學105學年度全國賽模擬賽pA

Subtasks

For Testdata: 0 ~ 1, Score: 27
For Testdata: 2 ~ 3, Score: 22
For Testdata: 4 ~ 5, Score: 17
For Testdata: 0 ~ 7, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 262144
1 1000 131072 262144
2 1000 131072 262144
3 1000 131072 262144
4 4000 131072 262144
5 4000 131072 262144
6 4000 131072 262144
7 4000 131072 262144