TopCoder

Doludu = =
我笨

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

24.7% (19/77)

Tags

Description

給你一些 1 到 $N$ 的排列(permutation),請你寫一個編碼的程式把這些 1 到 $N$ 的排列轉換成盡可能短的 0/1 字串,再寫一個解碼的程式把編碼得出的 0/1 字串轉換回原本的排列。

你可能會留意到這題的時限有那麼一點的少,不過你可以自己設定這題的時限喔!

Input Format

此程式對於每筆測資將會被執行三次,三次執行的 argv[1] 依序會是 012

第一次執行時,輸入只有一行包含兩個正整數 $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

# 第一次
2 5
# 第二次
2 5
1 2 3 4 5
5 1 3 4 2
# 第三次
2 5 10
0101010101
1010101010

Sample Output

# 第一次
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10 262144 65536 1
1 10 262144 65536 2
2 10 262144 65536 3
3 10 262144 65536 4
4 10 262144 65536 5
5 10 262144 65536 6