next_permutation の要領で ascending \((2, 2, ..., 2)\)-shuffle を列挙することで、\(O((2N - 1)!!)\) 時間で解くことができます。また列挙と同時に xor を計算することで \(O((2N - 1)!!)\) 時間に短縮できますが、私が実装してみたところ、速くはなりませんでした。

解法

\(1, \dots, 2N\) の置換 \(A\) が \((2, 2, ..., 2)\)-shuffle であるとは　\(A _ { 2 i - 1 } \le A _ { 2 i } \ ( 1 \le i \le N )\) を満たすことを言います。このようなもののうち ascending、すなわち \(A _ 1 \le A_3 \le A_5 \le \dots \le A_{2N - 1}\) であるものを列挙しましょう。

\(A\) が ascending \((2, 2, ..., 2)\)-shuffle として、辞書順で \(A\) より大きな最も小さな ascending \((2, 2, ..., 2)\)-shuffle を計算しましょう。これは後ろから順に見て、増やせる所があれば \(1\) 増やし、残りを昇順に埋めていけばよいです。

fn next_pairing(p: &mut [usize]) -> bool {
    let n = p.len();
    let mut used = 0_u32;
    for i in (0..n).rev() {
        used |= 1 << p[i];
        if i % 2 == 1 && p[i] + 1 < used.ilog2() as usize {
            p[i] = (used >> (p[i] + 1)).trailing_zeros() as usize + p[i] + 1;
            used ^= 1 << p[i];
            for i in i + 1..n {
                p[i] = used.trailing_zeros() as usize;
                used ^= 1 << p[i];
            }
            return true;
        }
    }
    false
}

参考記事: next_permutation と同様に列挙できるもの一覧

提出

Rust (26 ms): https://atcoder.jp/contests/abc236/submissions/47514980