TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

83.3% (15/18)

Submission's AC Ratio

23.0% (32/139)

Tags

Description

在準備進行融合儀式的時候,你發現你還需要將磁石,一個儀式所需要的祭器,擺放妥當。
相傳這$n$顆磁石在很久以前是個會動的生物,直到某個歷史重要人物在重要的比賽中獲得了亞軍後被眾人唾棄才漸漸失去活動的能力。

僅管失去了活動能力,這$n$顆磁石似乎還是有著自己的意識,所以他們對自己在儀式中被擺放的位置有所要求。這$n$顆編號為1到$n$的磁石,第$i$顆磁石很想要被擺在編號為$i$的環狀區域區塊。除此之外,每顆磁石還有一些特徵,分別是磁力值$m_i$以及影響範圍$d_i(2d_i+1\leq n)$。如果第$i$顆磁石已經在環狀區域中,那麼所有和他相隔$d_i-1$格以內(也就是說走$d_i$步以內可以到達)的區域的磁場值都會增加$m_i$。而由於磁石與磁場的排斥力,在某一格放入磁石所需花費的力氣即是該區域的磁場值。
雖然磁石放置的位置已經被決定了,不過聰明的你發現,藉由改變放入順序,你所花費的最大力氣可能變小。身為一名遊(ㄈㄟˊ)戲(ㄓㄞˊ)管理員,你當然不希望自己所需要花的最大力氣太大,因此你希望找出一個好的放入順序,使得你所花費的最大力氣最小化。

Input Format

第一行包含一個正整數$3\leq n\leq 400000$,代表磁石個數。
之後的$n$行中,每行有兩個正整數$m_i\leq 10^ 9, d_i \leq \frac{n-1}{2}$ ,分別代表第$i$顆磁石的磁力值以及影響範圍。

子任務(測資) 額外限制 分數
1 (0~4) $n\leq 10$ 7
2 (5~9) $n\leq 15$ 14
3 (10~14) $n\leq 10^ 4$ 46
4 (15~19) 33

Output Format

請輸出一行,包含$n$個正整數,代表使所需最大力氣最小化的一種放入順序。
注意:滿足條件的放入順序有很多種,你只需要輸出其中一種即可。

Sample Input 1

5
1 1
2 2
3 2
4 1
5 2

Sample Output 1

5 3 4 1 2

Hints

放入第5顆磁石花的力氣是0
放入第3顆磁石花的力氣是5
放入第4顆磁石花的力氣是8
放入第1顆磁石花的力氣是8
放入第2顆磁石花的力氣是9
所花費的最大力氣是9,並且不能再小了。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第六次模擬賽pD

Subtasks

No. Testdata Range Score
1 0~4 7
2 5~9 14
3 10~14 46
4 15~19 33

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 2500 131072 262144 4
16 2500 131072 262144 4
17 2500 131072 262144 4
18 2500 131072 262144 4
19 2500 131072 262144 4