2280 . 排列編碼
TopCoder
Tags
Description
給你一些 1 到 $N$ 的排列（permutation），請你寫一個編碼的程式把這些 1 到 $N$ 的排列轉換成盡可能短的 0/1 字串，再寫一個解碼的程式把編碼得出的 0/1 字串轉換回原本的排列。
你可能會留意到這題的時限有那麼一點的少，不過你可以自己設定這題的時限喔！
Input Format
此程式對於每筆測資將會被執行三次，三次執行的 argv[1] 依序會是 0、1、2。
第一次執行時，輸入只有一行包含兩個正整數 $T,N$，分別代表有幾個需要編碼的排列，以及排列的長度。
第二次執行時，輸入第一行有兩個兩個正整數 $T,N$，意義同第一次執行時的輸入。
接下來 $T$ 行，每行會有 $N$ 個正整數，即是給定的 1 到 $N$ 的排列。
第三次執行時的輸入即是第二次執行時你的程式的輸出。
對於所有的測資，$T\leq 10,N\leq 10^ 5,TN\leq 5\times 10^ 5$。
Output Format
第一次執行時請輸出一行包含兩個以空白隔開的正整數 $E,D\leq 10$。這會將第二次執行（編碼）的時限設為 $E/5$ 秒、第三次執行（解碼）的時限設為 $D/5$ 秒。
第二次執行時請輸出 $T+1$ 行。第一行有三個以空白隔開的正整數 $T,N,L$，$T,N$ 與輸入相同，$L$ 代表 0/1 字串的長度；接下來 $T$ 行，每一行包含一個長度為 $L$ 的 0/1 字串，代表排列編碼後的 0/1 字串。
第三次執行時請輸出 $T$ 行，每行有 $N$ 個以空白隔開的正整數，代表原本的排列。
對於每個子任務，如果你輸出了正確的排列，你在該子任務的分數會是 $\max\left(0,1+\frac{N\log_2 N-L}{2N}-\frac{6E+10D-16}{100}\right)\times x$，其中 $x$ 是該子任務的分數。如果你在每個子任務的分數都大於等於 $x/2$，你將會獲得一個 AC。
（有沒有 AC 不影響分數，只會影響 Ranklist、solved problems、user's AC ratio 等數據。）
Sample Input 1
2 5
# 第二次
2 5
1 2 3 4 5
5 1 3 4 2
# 第三次
2 5 10
0101010101
1010101010
Sample Output 1
5 5
# 第二次
2 5 10
0101010101
1010101010
# 第三次
1 2 3 4 5
5 1 3 4 2
Hints
這題可以拿到超過 100 分喔！
Problem Source
New TIOJ Contest pB
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | $N=10$ | 10 |
| 2 | 1 | $N=137$ | 14 |
| 3 | 2 | $N=1000$ | 22 |
| 4 | 3 | $N=6543$ | 15 |
| 5 | 4 | $N=33210$ | 16 |
| 6 | 5 | $N=10^ 5$ | 23 |