Submission

Score: 100

User: loop

Problemset: ประลอง

Language: cpp

Time: 0.006 second

Submitted On: 2026-10-10 18:41:23

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

// Probe: of all optimal splits, side 1 = the lexicographically largest set of positions
// (what a search that tries "side 2" before "side 1" for each unit and keeps the first optimum finds).
int n, k, v[105], off, W;
vector<bool> suf;   // suf[i][c][s]: units i..n-1 can give exactly c units with sum s - off
bool at(int i, int c, int s) { return s >= 0 && s < W && suf[((long)i * (k + 1) + c) * W + s]; }

int main() {
    scanf("%d", &n);
    int V = 0;
    long long total = 0;
    for (int i = 0; i < n; i++) { scanf("%d", &v[i]); total += v[i]; int a = v[i] < 0 ? -v[i] : v[i]; if (a > V) V = a; }
    k = n / 2; off = k * V; W = 2 * off + 1;
    suf.assign((long)(n + 1) * (k + 1) * W, false);
    suf[((long)n * (k + 1) + 0) * W + off] = true;
    for (int i = n - 1; i >= 0; i--)
        for (int c = 0; c <= k; c++)
            for (int s = 0; s < W; s++)
                if (at(i + 1, c, s) || (c >= 1 && at(i + 1, c - 1, s - v[i]))) suf[((long)i * (k + 1) + c) * W + s] = true;
    long long bestDiff = -1;
    for (int s = 0; s < W; s++) if (at(0, k, s)) {
        long long d = total - 2LL * (s - off); if (d < 0) d = -d;
        if (bestDiff < 0 || d < bestDiff) bestDiff = d;
    }
    vector<int> best;
    for (int s = 0; s < W; s++) {
        if (!at(0, k, s)) continue;
        long long d = total - 2LL * (s - off); if (d < 0) d = -d;
        if (d != bestDiff) continue;
        vector<int> seq;
        int pos = 0, c = k, rem = s;
        while (c > 0) {
            int i = n - 1;
            while (!at(i + 1, c - 1, rem - v[i])) i--;
            seq.push_back(i); rem -= v[i]; c--; pos = i + 1;
        }
        if (best.empty() && k > 0 ? true : seq > best) best = seq;
    }
    bool pick[105] = {false};
    for (size_t j = 0; j < best.size(); j++) pick[best[j]] = true;
    bool first = true;
    for (int i = 0; i < n; i++) if (pick[i]) { printf(first ? "%d" : " %d", v[i]); first = false; }
    printf("\n");
    first = true;
    for (int i = 0; i < n; i++) if (!pick[i]) { printf(first ? "%d" : " %d", v[i]); first = false; }
    printf("\n");
    return 0;
}