AGC 031 C. Differ by 1 Bit

C - Differ by 1 Bit

動く回数は必ず $2^N - 1$ 回なので $a$ と $b$ の立っている $bit$ の個数の偶奇は異なることが必要です．$0...$ から $1...$ などにはきれいに移動できるので自然に分割統治をしたくなります．頂点 $S$ と $T$ が今見ている部分の半分に含まれているかどうかで場合分けをすると帰納法によって経路 $S → T$ が必ずとれることがわかるので，これで解けました

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; (i) < (int) (n); (i) ++)
using namespace std;

vector<int> dfs(int left, int len, int s, int t) {
        assert(__builtin_popcount(s) % 2 != __builtin_popcount(t) % 2);
        if (len == 2) {
                return vector<int>{ s, t };
        }
        int m = left + len / 2;
        bool swapped = false;
        if (s > t) {
                swap(s, t);
                swapped = true;
        }
        if (s < m && m <= t) {
                int u = left;
                while (__builtin_popcount(u) % 2 == __builtin_popcount(s) % 2) {
                        u ++;
                }
                assert(u < m);
                int uu = u + len / 2;
                auto l = dfs(left, len / 2, s, u);
                auto r = dfs(m, len / 2, uu, t);
                for (auto it : r) {
                        l.push_back(it);
                }
                assert(l.size() == len);
                if (swapped) {
                        reverse(l.begin(), l.end());
                }
                return l;
        } else { 
                vector<int> res;
                if (s < m && t < m) {
                        auto l = dfs(left, len / 2, s, t);
                        int u = l[1];
                        int uu = u + len / 2;
                        int ss = s + len / 2;
                        auto r = dfs(m, len / 2, ss, uu);
                        res.push_back(s);
                        for (auto it : r) {
                                res.push_back(it);
                        }
                        for (int i = 1; i < l.size(); i ++) {
                                res.push_back(l[i]);
                        }
                } else {
                        auto r = dfs(m, len / 2, s, t);
                        int u = r[1];
                        int uu = u - len / 2;
                        int ss = s - len / 2;
                        auto l = dfs(left, len / 2, ss, uu);
                        res.push_back(s);
                        for (auto it : l) {
                                res.push_back(it);
                        }
                        for (int i = 1; i < r.size(); i ++) {
                                res.push_back(r[i]);
                        }
                }
                assert(res.size() == len);
                if (swapped) {
                        reverse(res.begin(), res.end());
                }
                return res;
        }
}

int main() {
        int n, a, b;
        scanf("%d%d%d", &n, &a, &b);
        if (__builtin_popcount(a) % 2 == __builtin_popcount(b) % 2) {
                puts("NO");
                return 0;
        }
        puts("YES");
        auto ans = dfs(0, (1 << n), a, b);
        assert(ans.size() == (1 << n));
        rep(i, ans.size()) {
                printf("%d ", ans[i]);
        }
        printf("\n");
        return 0;
}