ARC153C - ± Increasing Sequence

問題文

リンク：

C - ± Increasing Sequence

解説

$${p=(1, 2, \cdots, N)}$$に対して次の操作を好きな回数施しても，$${p}$$は狭義単調増加なままです．

• $${p}$$の prefix に -1 を足す．

• $${p}$$の suffix に 1 を足す．

簡単のため，$${s=\sum_{i=1}^N p_i A_i\gt 0}$$とします．

$${\sum_{i=1}^{pp} A_i=1}$$なる$${pp}$$，または$${\sum_{i=y}^{sn} A_i=-1}$$なる$${sn}$$が見つかれば，条件を満たす$${x}$$を構築できます．実際，$${x\leftarrow p}$$とした後，$${1\le i\le pp}$$に対して$${x_i\leftarrow p_i+s}$$とするか，$${sn\le i\le N}$$に対して$${x_i\leftarrow p_i-s}$$とすればよいです．$${s}$$は高々$${N^2\le 10^{10}}$$なので，$${|x_i|\le 10^{12}}$$を満たすことができます．

$${pp, sn}$$が存在しないときは，最初に示した操作を行っても$${s}$$は減少しません．ところで，最初に示した操作によって，$${p}$$を任意の狭義単調増加列に変化させることができます．したがって，任意の狭義単調増加列に対して$${s\gt 0}$$になります．すなわち，$${pp, sn}$$が存在しないときは条件を満たす$${x}$$が存在しません．

$${s\lt 0}$$の場合も同様に考えて存在判定・構築をすることができます．

提出コード

Submission #43959367 - AtCoder Regular Contest 153