暴力dfs

极简代码

#include <bits/stdc++.h>
#define debug(x) cout << #x << ' ' << x << '\n'
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
const int N = 1 << 18, mod = 1e9 + 7, inf = 0x3f3f3f3f;

struct node {
    int lose, win;
}a[N];
int k, n;

int dfs(int pos) {
    if (a[pos].lose > a[pos].win) return 0;
    if ((pos << 1) > n) return 1;

    int l = pos << 1, r = pos << 1 | 1;

    a[l].win = a[pos].win;
    a[r].win = a[pos].lose;
    if (dfs(l) && dfs(r)) return 1;

    a[l].win = a[pos].lose;
    a[r].win = a[pos].win;
    if (dfs(l) && dfs(r)) return 1;

    return 0;
}

void solve()
{
    cin >> k;
    n = (1 << k) - 1;
    for (int i = n; i; i --) {
        cin >> a[i].lose;
    }
    cin >> a[1].win;

    if (dfs(1)) {
        for (int i = n; i >= 1 << k - 1; i --) {
            cout << a[i].win << ' ' << a[i].lose << "\n "[i != k - 1];
        }
    }
    else cout << "No Solution" << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    solve();

    return 0;
}