1400 . 停車場 2
TopCoder
Tags
Description
NasaLee 去年推出的 CSIE-Bike 大獲成功！為了紀念停車場鞏固了他的政權，他特別成立了停車場部門，專門管理大大小小的停車場。他甚至在韭菜市的市中心建立了一個史上最大的停車場，停車場是一個 $2 \cdot 10^ 9 \times 2 \cdot 10^ 9$ 的正方形，可以同時容納非常多的各種不同大小的車。並且停車場是開放式的，可以從任何一個方向出入。
但是這麼大的停車場也衍生出一些問題：由於車子的大小不一樣，而停車場部門最近在處理邊境非法停車的問題而忘記畫好停車格了，因此逐漸有市民投訴後來的車的停放導致了他們無法把自己的車子移出去。為了解決這個問題，停車場部門決定把整個停車場淨空並重劃停車格。
停車場部門首先把停車場劃分成了 $[1, 2 \cdot 10^ 9] \times [1, 2 \cdot 10^ 9]$ 的格子，在這裡，一個單位是車道的大小，也就是所有的車子的寬度都是一個單位。而車子的長度可以是任意的大於 $1$ 的整數。停車場部門發現，每一台車子都剛好停在平行於座標軸的位置，再經過調查後發現，由於韭菜市的居民不喜歡改變計畫，也因此不喜歡轉彎，所以這些車子才會都是沿著出口的方向。另一個有趣的現象是所有車子都可以正著開，並且在此之上有些車子還可以倒著開，車子的方向一定是沿著他的長邊（長度大於 $1$ 的方向）。
因此停車場部門制定了以下移車規則：首先，為了滿足韭菜市民的喜好，車子不可以轉彎。再來，車子必須按照正著開或是倒著開的方向移動。最後，車子不能在移動時佔用同一個格子。並且為了防止工作人員操作失誤，每次只能移動一台車子，並且必須要等到車子完全離開停車場後才能移動下一台車。完全離開的意思是整台車子的任何一個部分都不在停車場的 $[1, 2 \cdot 10^ 9] \times [1, 2 \cdot 10^ 9]$ 的區域內。
由於停車場的車子太多了，停車場部門想請你幫忙規劃出一個移動序列可以把所有車子移出。另外，有可能不存在一個滿足當前移車規則的移動序列，這時候你要告訴停車場部門他們最多可以移出多少車子。
Input Format
輸入的第一行是一個正整數 $N$，代表共有幾台車。
接下來的 $N$ 行，第 $i$ 行有四個正整數 $X_{i, 1}, Y_{i, 1}, X_{i, 2}, Y_{i, 2}$ 跟一個字元 $D_i$。四個正整數代表車子佔據的空間，$D_i$ 可能是三種字元 $\texttt{+}, \texttt{-}, \texttt{?}$ 之一，分別代表向 $X$ 或 $Y$ 軸的正方向，負方向，或兩者皆可。方向使用的軸由車子的長邊決定。
- $1 \leq N \leq 10^ 5$
- $1 \leq X_{i, 1} \leq X_{i, 2} \leq 2 \cdot 10^ 9$
- $1 \leq Y_{i, 1} \leq Y_{i, 2} \leq 2 \cdot 10^ 9$
- $D_i \in \lbrace \texttt{+}, \texttt{-}, \texttt{?} \rbrace$
- 對於所有 $i$，$X_{i, 1} = X_{i, 2}$ 與 $Y_{i, 1} = Y_{i, 2}$ 恰有一個成立
- 保證沒有兩台車在開始時佔用同一個格子。
Output Format
你的輸出的第一行應該要是一個整數 $M$，代表可以移出多少車子。
接下來你應該要輸出 $M$ 行，第 $i$ 行由車子編號 $C_i$ 與方向 $D_i$ 組成，代表第 $i$ 部要移動第 $C_i$ 台車，沿著 $X$ 軸或 $Y$ 軸的 $D_i$ 方向移出。
輸出必須滿足：
- $1 \leq C_i \leq N$
- $C_i$ 互不相同
- $D_i \in \lbrace \texttt{+}, \texttt{-} \rbrace$。
Sample Input 1
5 1 3 1 4 + 3 1 4 1 - 3 2 3 3 - 3 4 4 4 ? 2 1 2 3 -
Sample Output 1
5 1 + 5 - 4 + 2 - 3 -
Sample Input 2
5 1 5 2 5 + 1 1 1 3 + 3 1 5 1 - 2 3 2 4 + 5 2 5 5 -
Sample Output 2
0
Sample Input 3
8 1835254751 1785891028 1835254751 1908608466 + 921402055 630098489 921402055 1459650706 ? 808780346 1571218910 829918507 1571218910 - 829918507 1541476519 829918507 1571218909 + 705555161 655102275 808780345 655102275 - 808780345 655102276 808780345 1571218910 - 64263821 613198861 1316862808 613198861 ? 887260626 32115194 987324500 32115194 -
Sample Output 3
8 2 + 1 + 7 + 8 - 5 - 6 - 3 - 4 +
Hints
底下是範例測試資料一的停車場狀況：
如圖：
- 為了方便起見，只畫了座標小於等於 $4$ 的區域。左下角是 $(1, 1)$，右上角是 $(4, 4)$。
一個長方形代表一台車，長方形中的箭頭代表可以移動的方向（正向），雙箭頭代表他可以正著開或倒著開。
一個合法的移動序列是：（按照順序）紅色向上移，橘色向下移，藍色向左移，綠色向左移，紫色向下移。
如果紫色向下移放到第一個則會撞到綠色，違反車子不能在移動時佔用同一個格子的限制。
停車場部門也不能藍色先向左移動一格再移動紅色，這樣違反車子必須要完全離開停車場才能移動下一台車的限制。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資。 | 0 |
| 2 | 0~25, 111~122 | $N \leq 3000$ | 14 |
| 3 | 0~2, 26~40, 101~110 | 車子的長度不超過 $20$。 | 19 |
| 4 | 41~51, 101~103, 111~113 | $D_i = \lbrace\texttt{?}\rbrace$ | 11 |
| 5 | 52~75, 104~110, 114~122 | $D_i \in \lbrace\texttt{+}, \texttt{-}\rbrace$ | 32 |
| 6 | 0~122 | 無特別限制。 | 24 |