Submission

Score: 60

User: Kidmaiok

Problemset: ประลอง

Language: cpp

Time: 0.005 second

Submitted On: 2026-10-13 09:57:43

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

#define ll long long
#define ull unsigned long long
#define space << ' '
#define nl << endl

struct Node {
    int index; 
    int prev;  
};

unordered_map<ll, int> dp[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<ll> a(n);
    ll total = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        total += a[i];
    }

    int k = n / 2;

    vector<Node> nodes;
    nodes.push_back({-1, -1});

    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int c = min(k, i + 1); c >= 1; c--) {
            for (auto [sum, prevNode] : dp[c - 1]) {
                ll newSum = sum + a[i];

                if (dp[c].count(newSum))
                    continue;

                int id = nodes.size();
                nodes.push_back({i, prevNode});
                dp[c][newSum] = id;
            }
        }
    }

    ll bestDiff = LLONG_MAX;
    int bestNode = 0;

    for (auto [sum, id] : dp[k]) {
        ll diff = llabs(total - 2 * sum);

        if (diff < bestDiff) {
            bestDiff = diff;
            bestNode = id;
        }
    }

    vector<bool> selected(n, false);

    while (bestNode != 0) {
        selected[nodes[bestNode].index] = true;
        bestNode = nodes[bestNode].prev;
    }

    for (int group = 0; group < 2; group++) {
        bool first = true;

        for (int i = 0; i < n; i++) {
            if (selected[i] == (group == 0)) {
                if (!first) cout << ' ';
                cout << a[i];
                first = false;
            }
        }

        cout << '\n';
    }
}