証明を与え、その証明を用いることで具体的な構築をします。

この証明は、公式解説における「貪欲法」が正当にまわることの証明も与えますが、構築はもっとnaiveな方法を取ることにします。（ \(A,B\) がソート済みでなくても動くような、直感的なアルゴリズムだと思います）

まず公式解説にも言及されている通り、全ての値に対して \(A, B\) に含まれる要素数が \(N\) 個以下であればYesです。これは以下のように証明できます。

もし、\(A[i] = B[i] (= x)\) であるような \(i\) が存在するとします。このとき、仮定より、\(x \ne A[j], x\ne B[j]\) であるような \(j\) が存在します。

なぜならば、残りのindexは \(N-1\) 個ありますが、\(x\) は \(N-2\) 個以下であるので、鳩の巣原理よりindexが \(1\) つ以上余るからです。

このとき、\(B[i]\) と \(B[j]\) をswapすることで、 \(A[i] \ne B[i], A[j] \ne B[j]\) にできます。（どちらも片方は \(x\) で片方は \(x\) ではないです）

\(A[i] = B[i]\) であるような \(i\) が存在する限り、この操作を繰り返すことで、有限回でこの操作は終わり、条件を満たす数列となります。よって証明できました。

以上の証明の操作をそのまま行えばよいです。

\(A[i] = B[i] (= x)\) であるような \(i\) を探すパートは \(A[i] \ne B[i]\) であった要素が \(A[i] = B[i]\) になることは無いことをふまえて、昇順に見ていくだけでよいです。

\(x \ne A[j], x\ne B[j]\) であるような \(j\) を探すパートは、各 \(x\) について「\(x \ne A[j], x\ne B[j]\) であるような \(j\) の集合」を（更新しながら）管理しておくことで達成されます。

しかし、これを愚直に全て管理しようとすると、\(O(N^2)\) かかります。そこで、\(x\) の \(A, B\) に含まれる要素数を \(c_x\) としたとき、鳩の巣原理の議論から「適当な \(c_x\) 個のindexのみ着目したとしても、そのような \(j\) がみつかること」を利用しましょう。すると、各 \(x\) について \(c_x\) 個のみ着目すればよいので、合計で \(O(N)\) となります。（実装例では \(0,1, \cdots ,c_x-1\) に着目しています）

実装例（PyPy）