TopCoder

User's AC Ratio

89.3% (25/28)

Submission's AC Ratio

66.7% (38/57)

Tags

Description

『陸行鳥大賽車』(チョコボレーシング 〜幻界へのロード〜)是1999年3月18日由史克威爾(SQUARE)發布的競速遊戲。

睽違已久,陸行鳥大賽車終於又推出了新的續作──「陸行鳥4D大賽車」,這款遊戲支援十萬人同時在線同時進行競速遊戲,在遊戲的過程中,可以在賽道上可以取得攻擊魔法石,攻擊其他對手,只要有玩家遭受攻擊的話,那麼這個玩家就會強制淘汰,從遊戲中離開。

此外還能取得衝刺魔法石,使用衝刺的話可以無條件的超越比自己目前名次高一名的玩家,但是最多只會超過一名,不會再超過更多人,如果當前使用衝刺的玩家已經是第一名的話那麼就不會使得玩家間的相對名次有任何變動。

現在遊戲管理員有一場比賽的事件紀錄(每個玩家使用攻擊魔法石、衝刺魔法石的紀錄),但是沒有這場比賽的結果,他想請你幫他依照事件紀錄計算出最後的結果。

Input Format

第一行包含一個整數$N( N \leq 10^5 )$,代表現在有$N$個玩家,編號$1 \sim N$的玩家目前分別為第$1 \sim N$名(編號$1$第$1$名、編號$2$第$2$名…)。

第二行包含一個整數$M( M \leq 50,000)$,代表接下來會依序發生$M$個事件。

接下來的$M$行,每行包含兩個整數$T_i , X_i ( 0 \leq T_i \leq 1 , 1 \leq X_i \leq N )$,$T_i$為$0$的時候,代表編號$X_i$的玩家遭受攻擊,然後離開遊戲;$T_i$ 為$1$的時候,代表編號$X_i$的玩家使用衝刺,無條件超越當前名次比他高一名的玩家。

測試資料保證玩家被淘汰之後不會再出現任何紀錄。

Output Format

輸出一行,包含$Y$個整數($Y$是剩餘玩家的數量),由名次小到大依序輸出,整數兩兩間以空白隔開,行末不能有多餘空白,並且換行。

Sample Input 1

7
9
0 6
1 3
1 5
0 7
1 1
1 5
1 3
1 2
0 2

Sample Output 1

3 1 5 4

Hints

1 2 3 4 5 6 7

(1). 編號6遭受攻擊。

1 2 3 4 5 7

(2). 編號3超車,超越編號2。

1 3 2 4 5 7

(3). 編號5超車,超越編號4。

1 3 2 5 4 7

(4). 編號7遭受攻擊。

1 3 2 5 4

(5). 編號1超車,但是編號1目前已經是第1名所以位置不變。

1 3 2 5 4

(6). 編號5超車,超越編號2

1 3 5 2 4

(7). 編號3超車,超越編號1。

3 1 5 2 4

(8). 編號2超車,超越編號5。

3 1 2 5 4

(9). 編號2遭受攻擊。

3 1 5 4

Problem Source

NEOJ Problem 21

Subtasks

No. Testdata Range Constraints Score
1 0~9 100

Testdata and Limits

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