No.1834 1D Gravity
タグ : / 解いたユーザー数 12
作問者 :
riano
/ テスター :
cn_449
👑 
ygussany
問題文
riano 君は、$1$ 次元の数直線上に星が並んでいる奇妙な宇宙のモデルで遊んでいます。
このモデルでは、時刻 $t=0$ において、無限に長い数直線上の $x=1,2,...,N$ に、それぞれ質量 $m_1,m_2,...,m_N$ である星が存在します。
ただし、$m_1,m_2,...,m_N$ は $1,2,...,N$ を並び替えた数列です。
また、時刻が $1$ 進むごとに、全ての星は同時に「両隣の座標のうち、より重い星が存在する方に移動する」ことを繰り返します。
厳密には、
- 時刻 $t_0$ において、ある星の座標が $x_0$ であるとき、同時刻に $x_0-1$ に存在する星の質量の最大値を $M_-$ 、$x_0+1$ に存在する星の質量の最大値を $M_+$ とする。 ただし、各座標に星が存在しない場合はそれぞれ $0$ とみなす。 この星の時刻 $t_0+1$ における位置は、$M_->M_+$ であれば座標 $x_0-1$ 、$M_-< M_+$ であれば座標 $x_0+1$ となる。
このとき、星々は十分な時間の後、隣接する $2$ 座標を交互に行き来するいくつかのグループに分かれた状態になります。 riano 君は、この状態を「終状態」と名付け、とても興味を持っています。 riano 君のかわりに、終状態に達する時刻と終状態において存在している星のグループの数を求めてください。
厳密には、ある整数 $t_\mathrm{end}$ を取ると、全ての星に対して
- ある整数 $x_\mathrm{end}$ を適切に選ぶと、この星は $t\geq t_\mathrm{end}$ において必ず $x=x_\mathrm{end}$ もしくは $x=x_\mathrm{end}+1$ に存在する。
【星の動きの参考図】
入力
$N$ $m_1$ $m_2$ $...$ $m_N$
- $2\leq N \leq 2\times 10^5$
- $1\leq m_i \leq N$ $(1\leq i \leq N)$
- $m_i\neq m_j$ $(i\neq j)$
- 入力は全て整数である
出力
「終状態に達する時刻」と「終状態における星のグループ数」を空白区切りで、順に整数で出力してください。 最後に改行してください。
サンプル
サンプル1
入力
5 3 4 1 5 2
出力
1 2
この入力は問題文中参考図の図 $1$ に対応します。
星の位置は図のように移り変わり、 $t=3$ の状態が $t=1$ の状態と等しいことから、この後は
星 $1,2,5$ からなるグループが $x=4,5$ を行き来し、星 $3,4$ のグループが $x=1,2$ を行き来することになります。
すなわち、$t=1$ 以降星々は $2$ 座標を交互に行き来する $2$ つのグループに分かれていると言えます。
したがって「終状態に達する時刻」は $1$、「終状態における星のグループ数」は $2$ となります。
厳密には、$t_\mathrm{end}=1$ 以降の各星の座標は、星 $3,4$ に対して $x_\mathrm{end}=1$、星 $1,2,5$ に対して $x_\mathrm{end}=4$ とすれば条件となる命題を満たせます。
なお、図の通り、複数の星が同じ座標に存在する場合でも合体などはせず、あくまで単体での質量で評価されることに注意してください。
サンプル2
入力
5 3 4 2 5 1
出力
2 1
この入力は問題文中の参考図の図 $2$ に対応します。 参考図の通り、この場合は $t_\mathrm{end}=2$ 以降、全ての星が $x=2,3$ を行き来することになりますので、 「終状態に達する時刻」は $2$、「終状態における星のグループ数」は $1$ となります。
サンプル3
入力
9 3 2 8 5 1 7 9 6 4
出力
2 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。