問題一覧 > 通常問題

No.1537 Please Do My Job for Me.

レベル : / AI推定難易度 : 1525 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 47
作問者 : pepper_aobuta / テスター : 57tggx logx ゅゅ とりゐ
お気に入りにしたユーザー ProblemId : 6523 / 自分の提出
問題文最終更新日: 2021-06-06 13:56:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
ゅゅちゃんお誕生日コンテスト (順位表) の他の問題:

Problem Statement


The Kingdom of Yuyu has $N$ cities $1,2,...,N$. City $1$ is the royal capital, where King Yuyu lives. The Kingdom of Yuyu also has $N$ distinct positive integers $A_1,A_2,...,A_N$ handed down through the generations.
Any $2$ cities in the Kingdom of Yuyu are connected by a road, and the length of the road connecting cities $i,j$ $(1\leq i < j\leq N)$ is $A_i\times A_j[\mathrm{m}]$.
Now, today is King Yuyu's birthday. Every year on the king's birthday, the king visits all the cities in the country. The kind-hearted King Yuyu wants to travel as long a distance as possible in order to show himself to more of his people. King Yuyu has entrusted me with planning the route of this trip, but I cannot figure out which route, among those that start from city $1$, pass through every city exactly once, and return to city $1$, has the maximum travel distance. So, please work out such a route for me. 　

Input

$N$
$A_1\ A_2\ ... \ A_N$
  • $2\leq N \leq 2\times 10^5$
  • $1 \leq A_i \leq 10^9$
  • $A_i \neq A_j$ when $i\neq j$
  • All input values are integers.

    • Output

    Output the numbers of the cities in the order they are visited, separated by single-byte spaces.
    For example, if the answer is the route that starts from city $1$, passes through cities $3,5,7,6,4,2$ in this order, and returns to $1$, output

    1 3 5 7 6 4 2 1

    If there are multiple answers, any of them will be accepted.

    Sample

    Sample 1
    Input
    2
1 2
    Output
    1 2 1

    Do not forget to output $1$ at the beginning and at the end.

    Sample 2
    Input
    3
1 4 12
    Output
    1 3 2 1

    Outputting 1 2 3 1 is also accepted.

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。