Submission

Score: 100

User: Karatat007

Problemset: ประลอง

Language: cpp

Time: 0.005 second

Submitted On: 2026-10-11 09:30:47

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

int n;
int bestdiff = INT_MAX;
vector<int>ansteam1,ansteam2;
vector<int>v;

void payayam(int i,vector<int> &team1,vector<int> &team2){
    if(i >= n){
        if(team2.size()-team1.size() > 1 or team2.size() < team1.size()) return;
        int sum1 = 0,sum2 = 0;
        for(auto x:team1)sum1+=x;
        for(auto x:team2)sum2+=x;
        if(abs(sum1-sum2)<bestdiff){
            bestdiff = abs(sum1-sum2);
            ansteam1 = team1;
            ansteam2 = team2;
        }
        return;
    }
    team1.push_back(v[i]);
    payayam(i+1,team1,team2);
    team1.pop_back();
    team2.push_back(v[i]);
    payayam(i+1,team1,team2);
    team2.pop_back();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    v.resize(n);
    for(int i = 0;i < n;++i){
        cin >> v[i];
    }
    vector<int> tempa,tempb;
    payayam(0,tempa,tempb);
    for(auto m : ansteam1) cout << m << ' ';
    cout << '\n';
    for(auto m : ansteam2) cout << m << ' ';
}
    */
#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 > 10000) abort();
    if (V > 3000) 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;
}