AtCoder Grand Contest 001: D - Arrays and Palindrome

,

solution

等式制約の片側(つまり「先頭の a1 文字、続く a2 文字、さらに続く a3 文字 … はすべて回文である。」)を図示すると次のようになる。 $a = ( 5, 8, 1, 3 )$である。

          +-------------+
+-------+ | +---------+ |
| +---+ | | | +-----+ | |   +---+
| |   | | | | | +-+ | | |   |   |
A B C b a D E F G g f e d H I J i

このようなグラフを$b$についても作って繋げたときに連結になっていればよい。 各点の次数は高々$2$なので、連結であれば木か閉路のどちらか。 $a$中に奇数の項が$3$つ以上あるとき次数を考えれば明らかに不可能である。

$a$中の奇数の項が$2$つ以下なら可能である。 これは両端に奇数の項を配し、偶数の項には$1$だけずらして以下のように重ねればできる。

+-------------+
| +---------+ |
| | +-----+ | |
| | | +-+ | | |
A B C D d c b a z
  | | | +-+ | | |
  | | +-----+ | |
  | +---------+ |
  +-------------+

implementation

#!/usr/bin/env python3
def solve(n, m, a):
    odd = []
    even = []
    for a_i in a:
        if a_i % 2 == 0:
            even += [ a_i ]
        else:
            odd += [ a_i ]
    if len(odd) >= 3:
        return None
    a, b = [], []
    if odd:
        x = odd.pop()
        a += [ x ]
        b += [ x - 1 ]
    else:
        x = even.pop()
        a += [ x ]
        b += [ x - 1 ]
    a += even
    b += even
    if odd:
        x = odd.pop()
        a += [ x ]
        b += [ x + 1 ]
    else:
        b += [ 1 ]
    return a, b

n, m = map(int, input().split())
a = list(map(int, input().split()))
it = solve(n, m, a)
if it is None:
    print('Impossible')
else:
    a, b = it
    b = list(filter(lambda b_i: b_i, b))
    print(*a)
    print(len(b))
    print(*b)