(より詳しい解説は後日ブログで公開します)

まず非負整数 \(a_1, \ldots, a_M, b_1, \ldots, b_N\) が与えられたときありうるかの判定方法を考えます．\(a_i\) や \(b_j\) は昇順としてよいです．累積和を \(f_i = \sum_{k=1}^i a_k,\, g_j = \sum_{k=1}^j b_k\) とします．

判定は \(4\) 匹組から各動物へのフロー (あるいは勝数ぶん頂点を増やしてマッチング) で書けるので，最小カット (あるいは Hall の定理) を考えることで，次の条件を見ればよいことになります：

• \(f_i + g_j \ge \binom{i}{2} \binom{j}{2}\) (\(0 \le i \le M,\, 0 \le j \le N\))
• \(f_M + g_N = \binom{M}{2} \binom{N}{2}\)

元の問題に戻ります．\(A_i\) をソートして累積和 \(f_i\) をとります．辞書順最小の \(b\) は存在するなら昇順です．上の条件から \(b_j\) の累積和の下界 \(g_j \ge G_j := \max_i \left( \binom{i}{2} \binom{j}{2} - f_i \right)\) が得られます．すると以下のようになります：

• \(f_M + G_N < \binom{M}{2} \binom{N}{2}\) とはなりません．
• \(f_M + G_N = \binom{M}{2} \binom{N}{2}\) のとき，\(g_j = G_j\) が条件を満たします．これは \(G_j\) が広義単調増加凸関数の max なので広義単調増加凸関数となるからです．対応する \(b_j\) の辞書順最小性も先頭から貪欲にとれているので従います．
• \(f_M + G_N > \binom{M}{2} \binom{N}{2}\) のとき解はありません．

\(G_j\) を求める部分は convex hull trick として知られています．入力のソートを除いて \(O(M+N)\) 時間でできます．