[Codeforces] Educational Codeforces Round 94 (Rated for Div. 2) C. Binary String Reconstruction

問題

方針

文字列 \( w \) と自然数 \( x \) が与えられたとき次の条件を満たす文字列 \( w \) を答えます。

  1. \( i – x \geq 0 \wedge w_{i-x} = 1 \) ならば \( s_i = 1 \)
  2. \( i + x \leq n \wedge w_{i+x} = 1 \) ならば \( s_i = 1 \)
  3. 1 と 2 を両方満たさないとき \( s_i = 0\)

まず初めに、\( w \) を 1 だけからなる文字列とします。条件 3 から、\( s_i = 0\) となる整数 \( i \) に対して、\( w_{i -x} = 0 \) 、\( w_{i + x} = 0 \) とします。

次に、\( s_{i} = 1 \) となる整数 \( i \) に対して、 \( w_{i – x} = 1 \vee w_{i + x} = 1 \) を満たす \( i \) が存在するとき、条件を満たす文字列は存在しますが、そうではないとき答えは-1となります。

コード