TopCoder

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

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Description

「咚!!」 勇者帥氣地推開大門,準備跟魔王拼命。
正當勇者的劍準備出鞘,勇者定神一看……「咦!怎麼魔王的等級比我高了10倍!」
這完完全全沒有道理,畢竟勇者已經達成所有條件,獲得了理論上最強的技能了。
「嘖!這遊戲一定不是設計給人過關的!」勇者憤怒道。

不論如何,現在最重要的事情就只有逃命了。

要知道,魔王房間對外的通道只有由$N$根石柱由內往外排成一直線的道路,剩下的地方都被岩漿所包圍。石柱由內而外從1編號到$N$,編號為$i$的石柱的位置為$x_i$。勇者從最內側的石柱出發,藉由不斷的往外跳到另一根石柱(一次可以跳過任意根石柱,但不能往內跳),最終抵達最外側的石柱以逃出魔王房間。這$N$根石柱的高度都不同,而這是有用意的:愈高的石柱會愈受到魔王的魔力影響,所以勇者就需要耗費愈多的魔力才能在其上跳躍。當然,兩個石柱之間距離愈遠,勇者也會需要花費愈多的魔力進行跳躍。如果兩個石柱$A,B$之間的距離是$d$(也就是兩個石柱位置的差),而兩個石柱的高度分別為$a,b$,那麼勇者就需要耗費$(10^ 5+1)(a+b+d)$的魔力才能從$A$跳到$B$。

然而,這個勇者不是普通的勇者。他有一個特殊技能:所耗費的魔力可以轉換成怒氣值,使之後的移動可以更不耗費魔力。具體來說,勇者的怒氣值是一個$0$到$10^ 5$的整數。如果勇者在跳躍當下的怒氣值是$C$,那麼他只需要$(10^ 5+1-C)(a+b+d)$的魔力就可以進行上述的跳躍。而跳躍所花費的魔力會在跳躍完成後轉換為怒氣值:如果勇者從開始逃命到當前所花費的總魔力是$p$,那麼他的怒氣值就會變成$\min\left(10^ 5,\left\lfloor \sqrt[3]{p}\right\rfloor\right)$。

然而,這個勇者是個高傲的勇者,因此他連逃命都想要展示他高超的路徑規劃能力。具體來說,他的路徑會滿足,對於所有途中經過的石柱,他抵達該石柱所用的魔力都要愈小愈好。當然這裡的「愈小愈好」是有條件的:如果對於某個石柱$X$,有某條起點到$X$的路徑$S$所耗費的魔力並非最小,那麼所有以$S$開頭的路徑都不會被考慮。
(例如,如果$1 \rightarrow 2 \rightarrow 3$耗費的魔力值大於$1\rightarrow 3$,那麼就算$1\rightarrow 2\rightarrow 3\rightarrow 4$耗費的魔力值小於$1\rightarrow 3\rightarrow 4$,勇者仍然不會選擇$1\rightarrow 2\rightarrow 3\rightarrow 4$這條路徑。)

你,身為勇者的競爭者,對勇者這樣高傲的行為感到十分不悅,因此你決定在他逃命的途中偷襲他。所以,你得先寫個程式,算出一條勇者可能採用的路徑。

Input Format

第一行有一個正整數$3\leq N\leq 10^ 6$,代表柱子個數。
第二行有$N$個非負整數$h_1,h_2,\dots,h_N\leq 10^ 9$,代表由內到外柱子的高度。
第三行有$N$個非負整數$x_1,x_2,\dots,x_N$,代表由內到外柱子的位置,其中$0=x_1<x_2<\cdots<x_N\leq 10^ {11}$。

Output Format

請輸出能使勇者魔力耗費最小的一條路線。第一行請輸出一個正整數$K$,代表勇者會經過$K$個石柱(包含最內側與最外側兩個);接下來$K$行每行輸出一個正整數,代表勇者依序經過的石柱編號。

Sample Input

4
1 2 0 4
0 3 6 100

Sample Output

3
1
3
4

Hints

範例測資中勇者有四條路徑可以選擇:$1\rightarrow 2\rightarrow 3\rightarrow 4$、$1\rightarrow 3\rightarrow 4$、$1\rightarrow 2\rightarrow 4$、$1\rightarrow 4$。然而,由於$1\rightarrow 2\rightarrow 3$耗費的魔力大於$1\rightarrow 3$,所以$1\rightarrow 2\rightarrow 3\rightarrow 4$這條路徑不會被勇者考慮。而另外三條路徑所耗費的魔力則分別是10491481、10891457與10500105。

Problem Source

Subtasks

No. Testdata Range Score
1 0~15 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 262144 262144 1
1 2500 262144 262144 1
2 2500 262144 262144 1
3 2500 262144 262144 1
4 2500 262144 262144 1
5 2500 262144 262144 1
6 2500 262144 262144 1
7 2500 262144 262144 1
8 2500 262144 262144 1
9 2500 262144 262144 1
10 2500 262144 262144 1
11 2500 262144 262144 1
12 2500 262144 262144 1
13 2500 262144 262144 1
14 2500 262144 262144 1
15 2500 262144 262144 1