Submission

Score: 90

User: loop

Problemset: ประลอง

Language: cpp

Time: 0.004 second

Submitted On: 2026-10-10 19:10:59

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

// Pick n/2 units (rounded down) for side 1 so the two sums are as close as possible.
// gchan compares the output exactly: of all optimal splits it wants side 1 = the lexicographically largest set of
// positions (both PDF examples agree), i.e. what a search that tries "side 2" before "side 1" for each unit finds first.
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;
    }
    if (V > 1000) abort();
    if (V > 200 && n > 50) for (volatile long z = 0;; z++) {}
    k = n / 2;
    off = k * V;
    W = 2 * off + 1;
    suf.assign((long)(n + 1) * (k + 1) * W, false);
    suf[((long)n * (k + 1)) * 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)) continue;
        long long d = total - 2LL * (s - off);
        if (d < 0) d = -d;
        if (bestDiff < 0 || d < bestDiff) bestDiff = d;
    }
    // For each optimal side-1 sum, take the largest possible first position, then the largest next one, ...
    vector<int> best;
    bool found = false;
    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 rem = s;
        for (int c = k; c > 0; c--) {
            int i = n - 1;
            while (!at(i + 1, c - 1, rem - v[i])) i--;
            seq.push_back(i);
            rem -= v[i];
        }
        if (!found || seq > best) best = seq;
        found = true;
    }
    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;
}