問題一覧 > 通常問題

No.1537 私の代わりに仕事やっといてください。

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 43
作問者 : pepper_aobutapepper_aobuta / テスター : 57tggx57tggx logxlogx ゅゅゅゅ とりゐとりゐ
1 ProblemId : 6523 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-06 13:56:13

問題文


　ゅゅ王国には $N$ 個の都市 $1,2,...,N$ があります。都市 $1$ は王都であり、ゅゅ国王はここに住んでいます。また、ゅゅ王国には代々伝わる $N$ 個の相異なる正の整数 $A_1,A_2,...,A_N$ が存在します。
　ゅゅ王国にある都市はどの $2$ 都市間も道路で結ばれており、都市 $i,j$ $(1\leq i < j\leq N)$ 間を結んでいる道路の長さは $A_i\times A_j[\mathrm{m}]$ です。
　さて、今日はゅゅ国王の誕生日です。ゅゅ王国では毎年、国王の誕生日に国王が全国のすべての都市を訪れて回ります。心優しいゅゅ国王は、より多くの国民に自身の姿を見せるため、なるべく長距離の移動をしようと考えています。私はゅゅ国王にこの旅の移動経路の計画を任されたのですが、都市 $1$ を出発してどの都市もちょうど一度ずつ通って都市 $1$ に戻ってくる経路のうち、移動距離が最大になるような経路がわかりません。そこで、私の代わりにそのような移動方法を考えてください。 　

入力

$N$
$A_1\ A_2\ ... \ A_N$
  • $2\leq N \leq 2\times 10^5$
  • $1 \leq A_i \leq 10^9$
  • $i\neq j$ のとき $A_i \neq A_j$
  • 入力はすべて整数

    • 出力

    　通る順番に都市の番号を半角スペースで区切って出力してください。
    　例えば、都市 $1$ を出発して都市 $3,5,7,6,4,2$ の順番で通って $1$ に戻ってくる経路が答えであるとき

    1 3 5 7 6 4 2 1
    と出力してください。
    　また、複数の答えが存在する場合、どれを解答しても正解となります。

    サンプル

    サンプル1
    入力
    2
1 2
    出力
    1 2 1

    初めと終わりに $1$ を出力するのを忘れないでください。

    サンプル2
    入力
    3
1 4 12
    出力
    1 3 2 1

    1 2 3 1 と出力しても正解になります．

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