TopCoder

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

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

76.2% (16/21)

Tags

Description

在2017的IOI國手群中有傳奇的事情發生,例如說存在一個三角形的定義完全不同的空間、或者某種會跑的神秘物種等等。然而其中稱得上是經典的,大概就是唬爛了吧!

事情是這樣的。在這個國手群中有個人對唬爛有特殊的喜好,他的經典名句就是:「那你一定在唬爛啊」。當然,好的唬爛也不是隨便說說就可以想到的,因此他們總是會互相交流各式各樣的唬爛,以持續精進唬爛能力。

有一天,這個人突發奇想,想要把很多個唬爛融合在一起,以創造更高品質的唬爛。因此,他們首先選出了$N$則唬爛,並且依照連貫性將這些唬爛排成一排,簡稱「唬爛接龍」。接著,他們可以選擇唬爛接龍中連續三則唬爛,並將中間那則的精髓融合到它的前後兩則唬爛當中,接著把中間那則唬爛拿掉。這個動作可以不斷重複,一直到唬爛接龍中只剩下兩則唬爛為止。

當然,融合唬爛的這個動作是很花時間的,假設選擇的連續三則唬爛的長度分別是$a,b,c$,那他們就需要花$abc$單位的時間完成融合的動作(融合前後唬爛的長度不會改變)。但國手們其實也都很忙,所以不想浪費太多時間做這件事情。因此,你的任務就是寫一個程式計算總花費時間最少的融合方法。

例如若$N=5$,五則唬爛的長度分別是13,17,16,11,15,則可以先選17,16,11,融合後變成13,17,11,15;再選13,17,11,變成13,11,15;最後再選剩下的三則,這樣總共的花費是$17\times16\times11+13\times17\times11+13\times11\times15=7568$,這也是所有融合方法中花費最小的一種。

當然,因為他們是資訊國手的關係,所以也想順便考考你會不會資訊界中非常重要的一種資料結構:二元樹。恰好,假如把「融合」這個動作看成一種兩組唬爛((前,中)一組、(中,後)一組)進行的二元運算的話,那整個融合過程可以被表示成一個運算式。例如上例中,若把唬爛從0編號到$N-1$,那該融合過程就是$((0,1)+((1,2)+(2,3)))+(3,4)$,可以用運算樹的前序遍歷表示成$+,+,(0,1),+,(1,2),(2,3),(3,4)$。若把所有的$+$換成$-1$,把一組唬爛換成前面那一組的編號,運算式便可以簡記成$-1,-1,0,-1,1,2,3$,稱這是這個融合策略的前序表示法。

因此,請你寫一個函數,計算對於任意的唬爛接龍,花費時間最少的融合方法的前序表示法長什麼樣子。

Input Format

本題沒有輸入,如果你輸入了任何東西可能會導致各種不可預期的結果(?)。

#include "lib2014.h"之後實作下列一個函數。如果你的函數名稱不對或者長得不像下面那一行,你將會獲得一個CE。

void Solve(int N, __int128 l[], int ans[]);:評分程式會呼叫這個函數,並傳入唬爛接龍的長度$N$以及每則唬爛的長度$l_i$。你必須將你的融合策略的前序表示法(長度$2N-3$)存入陣列ans當中。

在同一次執行中,Solve可能會被呼叫很多次(最多8次),所以請確保這個函數有做好初始化的動作。

對於所有測資,$3\leq N\leq 10^ 6; 1\leq l_i\leq 10^ 9$。
下表中以$C_{\text{opt}}$代表最佳融合策略的總花費時間,$C$代表Solve回傳的融合策略的總花費時間。

子任務(測資) 額外限制 分數
1 (0) $N=3$ 1
2 (0~1) $N\leq 20$ 37
3 (0~2) $N\leq 500$ 62
4 (0~3) $N\leq 5000$ 30
5 (0~4) $N\leq 10^ 5$ 42
6 (5) $h_i$為非遞減序列 17
7 (5~6) $h_i$先遞增後遞減 56
8 (7) 只要$C\leq 2C_{\text{opt}}$就會被視為正確 28
9 (7~8) 只要$C\leq 1.25C_{\text{opt}}$就會被視為正確 32
10 (0~9) 95

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

Sample Input

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
2
5
13 17 16 11 15
3
10 20 30

Sample Output

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見Hints)使用。
-1 -1 0 -1 1 2 3
7568
-1 0 1
6000

Hints

這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受的輸入格式如下:
首先輸入$T$(測資筆數);對於每一筆測資,依序輸入$N,l_0,l_1,\cdots,l_{N-1}$。

對於每一次呼叫Solve函數,此程式會輸出兩行,第一行為回傳的融合策略,第二行為這個融合策略的總花費時間。

以下是一個保證格式正確(不會CE也不會REMLE)但只能讓你獲得1分的範例程式:

#include "lib2014.h"

void Solve(int N, __int128 h[], int ans[]) {
  ans[0] = -1;
  ans[1] = 0;
  ans[2] = 1;
}

Problem Source

Problem Set / Description by Yihda Yol

Subtasks

For Testdata: 0 ~ 0, Score: 1
For Testdata: 0 ~ 1, Score: 37
For Testdata: 0 ~ 2, Score: 62
For Testdata: 0 ~ 3, Score: 30
For Testdata: 0 ~ 4, Score: 42
For Testdata: 5 ~ 5, Score: 17
For Testdata: 5 ~ 6, Score: 56
For Testdata: 7 ~ 7, Score: 28
For Testdata: 7 ~ 8, Score: 32
For Testdata: 0 ~ 9, Score: 95
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 500 768432 65536
1 4500 768432 65536
2 4500 768432 65536
3 8500 768432 65536
4 8500 768432 65536
5 8500 768432 65536
6 8500 768432 65536
7 8500 768432 65536
8 8500 768432 65536
9 8500 768432 65536