提出 #67333682

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int *a;
    int n;

public:
    Solution(int sz) {
        n = sz;
        a = new int[1 << n];
    }

    void input() {
        for (int i = 0; i < (1 << n); ++i) {
            cin >> *(a + i);
        }
    }

    vector<int> solve() {
        return build(0, 1 << n);
    }

    void output() {
        vector<int> res = solve();
        for (size_t i = 0; i < res.size(); ++i) {
            cout << res[i] << (i + 1 < res.size() ? ' ' : '\n');
        }
    }

private:
    vector<int> build(int start, int len) {
        if (len == 1) {
            return { *(a + start) };
        }

        int half = len >> 1;
        vector<int> L = build(start, half);
        vector<int> R = build(start + half, half);

        vector<int> opt1, opt2;
        stack<int> st;

        for (int x : L) st.push(x);
        for (int x : R) st.push(x);
        while (!st.empty()) {
            opt1.push_back(st.top());
            st.pop();
        }
        reverse(opt1.begin(), opt1.end());

        for (int x : R) st.push(x);
        for (int x : L) st.push(x);
        while (!st.empty()) {
            opt2.push_back(st.top());
            st.pop();
        }
        reverse(opt2.begin(), opt2.end());

        return (opt1 < opt2) ? opt1 : opt2;
    }
};

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        Solution *sol = new Solution(N);
        sol->input();
        sol->output();
        delete sol;
    }
    return 0;
}

提出情報

ジャッジ結果