問題概要

総和が $N$ 、長さが $M$ の正の整数からなる数列 $A_1, A_2, \dots, A_M$ が与えられる。

これを適切に並び替えたもの $a_1, a_2, \dots, a_M$ を作り
もう一つの総和が $N$ の数列 (長さはなんでもよい) $b_1, b_2, \dots$

を作ることで

文字列の先頭から $a_1, a_2, \dots$ 文字がそれぞれ回文
文字列の先頭から $b_1, b_2, \dots$ 文字がそれぞれ回文

という条件を満たす任意の長さ $N$ の文字列が、すべての文字が同じ文字でなければならないようなものを一つ求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le M \le 100$

考えたこと

色々実験してると不思議な気持ちになる問題だった。
サンプルについて、どうやったらできるかを色々組んで遊んでた。できなくなるパターンとして

端点になる部分が 3 箇所以上発生してしまう
輪っかになってしまう

というのがあるなーと思った。この辺りでサンプル 3 がなぜ No なのかを考えることにした。この考察が割とメインな印象。

55 10
1 2 3 4 5 6 7 8 9 10

目をつけたのは

長さが奇数の区間だと真ん中にエッジが張られない

ということ。つまり長さが奇数の区間が多いと、張られるエッジの本数が小さくなって全体を連結にできないだろうと。

全体を連結にするためには最低でも $N-1$ 本以上のエッジが必要になる。具体的に奇数が何個あったら駄目なのかを求めると 3 個になった。1, 2, ..., 10 には奇数が 5 個あるから駄目だ。

奇数が 0, 1, 2 個のとき

奇数が 0〜2 個のときはどうだろう。。。
一応できそうなことがわかってきた。色々実験してみて例えば

3 6 2 4 7

とかに対しては

4 6 2 4 6

とか「概ね 1 個ずらし」にすればできそうだとわかった。知見として

「長さ $N$ の回文において、長さ $N-1$ の部分も回文だったら全体が同じ文字になる」

くらいのことは頭の片隅においてもよさそうな気がしてきた。あとは $a, b$ とを合わせて奇数が 2 個いないにおさまるように調整して通った。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M; cin >> N >> M;
    vector<int> A(M);
    for (int i = 0; i < M; ++i) cin >> A[i];

    // 1 個の場合
    if (A.size() == 1) {
        cout << A[0] << endl;
        if (A[0] > 1) {
            cout << 2 << endl;
            cout << A[0]-1 << " " << 1 << endl;
        }
        else {
            cout << 1 << endl;
            cout << 1 << endl;
        }
        return 0;
    }

    // 偶数 / 奇数
    vector<int> odd, even;
    for (int i = 0; i < A.size(); ++i) {
        if (A[i] % 2 == 1) odd.push_back(A[i]);
        else even.push_back(A[i]);
    }
    if (odd.size() > 2) {
        cout << "Impossible" << endl;
        return 0;
    }

    // 求める
    vector<int> resA;
    if (odd.size() >= 1) resA.push_back(odd[0]);
    for (int i = 0; i < even.size(); ++i) resA.push_back(even[i]);
    if (odd.size() == 2) resA.push_back(odd.back());

    vector<int> resB;
    resB.push_back(resA[0] + 1);
    for (int i = 1; i+1 < resA.size(); ++i) resB.push_back(resA[i]);
    if (resA.back() > 1) resB.push_back(resA.back() - 1);

    // 出力
    for (int i = 0; i < resA.size(); ++i) {
        if (i) cout << " ";
        cout << resA[i];
    }
    cout << endl;
    cout << resB.size() << endl;
    for (int i = 0; i < resB.size(); ++i) {
        if (i) cout << " ";
        cout << resB[i];
    }
    cout << endl;
}