Submission

Score: 60

User: loop

Problemset: ประลอง

Language: cpp

Time: 0.004 second

Submitted On: 2026-10-10 18:34:02

#include <cstdio>
#include <vector>
using namespace std;

// Pick n/2 units (rounded down) for side 1 so the two sums are as close as possible.
// par[c][s] = the unit that first made "c units with sum s" reachable; following it back rebuilds the choice.
int main() {
    int n, v[105], V = 0;
    long long total = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        total += v[i];
        int a = v[i] < 0 ? -v[i] : v[i];
        if (a > V) V = a;
    }
    int k = n / 2, off = k * V, width = 2 * off + 1;
    vector<vector<signed char> > par(k + 1, vector<signed char>(width, 0));
    par[0][off] = -1;                                   // empty choice, sum 0
    for (int i = 1; i <= n; i++)
        for (int c = (i < k ? i : k); c >= 1; c--)
            for (int s = 0; s < width; s++) {
                if (par[c - 1][s] == 0) continue;
                int t = s + v[i];
                if (t < 0 || t >= width || par[c][t] != 0) continue;
                if (par[c - 1][s] == -1 && c - 1 != 0) continue;
                par[c][t] = (signed char)i;
            }
    int best = -1;
    long long bestDiff = 0;
    for (int s = 0; s < width; s++) {
        if (par[k][s] == 0) continue;
        long long sum1 = s - off, d = total - 2 * sum1;
        if (d < 0) d = -d;
        if (best < 0 || d < bestDiff) { best = s; bestDiff = d; }
    }
    bool pick[105] = {false};
    int s = best;
    for (int c = k; c >= 1; c--) {
        int i = par[c][s];
        pick[i] = true;
        s -= v[i];
    }
    bool first = true;
    for (int i = 1; i <= n; i++) if (pick[i]) { printf(first ? "%d" : " %d", v[i]); first = false; }
    printf("\n");
    first = true;
    for (int i = 1; i <= n; i++) if (!pick[i]) { printf(first ? "%d" : " %d", v[i]); first = false; }
    printf("\n");
    return 0;
}