Submission #4891161

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
using namespace std;

vector<int> func(int n, int k) {
    default_random_engine gen;
    assert (k % 2 == 1);
    vector<int> p(1 << n);
    REP (i, 1 << n) {
        p[i] = (i ^ (i >> 1));
    }
    assert (__builtin_popcount(p.back()) == 1);
    while (__builtin_popcount(p.back()) < k) {
        int found = -1;
        double max_value = -1;
        REP3 (i, 1, 1 << n) {
            if (__builtin_popcount(p[i - 1] ^ p.back()) == 1 and __builtin_popcount(p[i]) > __builtin_popcount(p.back())) {
                assert (__builtin_popcount(p[i]) == __builtin_popcount(p.back()) + 2);
                double value = 1 + uniform_real_distribution<double>()(gen);
                if (max_value < value) {
                    max_value = value;
                    found = i;
                }
            }
            if (__builtin_popcount(p[i - 1] ^ p.back()) == 1 and __builtin_popcount(p[i]) == __builtin_popcount(p.back())) {
                double value = uniform_real_distribution<double>()(gen);
                if (max_value < value) {
                    max_value = value;
                    found = i;
                }
            }
        }
        assert (found != -1);
        reverse(p.begin() + found, p.end());
    }
    assert (__builtin_popcount(p.back()) == k);
    return p;
}

bool bit(int x, int i) {
    return x & (1 << i);
}

int swap_bits(int x, int i, int j) {
    if (bit(x, i) != bit(x, j)) {
        x ^= 1 << i;
        x ^= 1 << j;
    }
    return x;
}

vector<int> solve1(int n, int b) {
    int k = __builtin_popcount(b);
    if (k % 2 == 0) {
        return vector<int>();
    }
    vector<int> p = func(n, k);
    REP (i, 1 << n) {
        int c = p.back();
        REP (k1, n) {
            if (bit(c, k1) != bit(b, k1)) {
                REP (k2, n) if (k2 != k1) {
                    if (bit(c, k2) != bit(b, k2) and bit(c, k2) == bit(b, k1)) {
                        c = swap_bits(c, k1, k2);
                        p[i] = swap_bits(p[i], k1, k2);
                        break;
                    }
                }
            }
        }
        assert (c == b);
    }
    assert (p.front() == 0);
    assert (p.back() == b);
    return p;
}

vector<int> solve(int n, int a, int b) {
    vector<int> p = solve1(n, b ^ a);
    if (p.empty()) return p;
    REP (i, 1 << n) {
        p[i] ^= a;
    }
    return p;
}

int main() {
    int n, a, b; cin >> n >> a >> b;
    vector<int> p = solve(n, a, b);
    if (p.empty()) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        for (int p_i : p) {
            cout << p_i << ' ';
        }
        cout << endl;

        // check
        assert (p.front() == a);
        assert (p.back() == b);
        REP (i, (1 << n) - 1) {
            assert (__builtin_popcount(p[i] ^ p[i + 1]) == 1);
        }
    }
    return 0;
}

Submission Info

Judge Result