Submission

Score: 60

User: NJTYTYTY

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2026-08-11 19:48:18

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    // เพิ่มความเร็วในการ Read/Write I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> a(n);
    int min_val = 0;
    int total_orig_sum = 0;

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

    // 1. Shift Offset เพื่อเปลี่ยนค่าติดลบให้ไม่เป็นลบ
    int C = -min_val;
    vector<int> a_shift(n);
    int max_a_shift = 0;
    for (int i = 0; i < n; i++) {
        a_shift[i] = a[i] + C;
        if (a_shift[i] > max_a_shift) {
            max_a_shift = a_shift[i];
        }
    }

    int k = n / 2; // จำนวนยูนิตของฝ่ายที่ 1
    int max_sum = k * max_a_shift;

    // 2. สร้างตาราง DP: dp[i][c][s]
    // dp[i][c][s] = true หมายถึง ใช้ c ยูนิตจาก i ยูนิตแรก ได้ผลรวมเป็น s
    vector<vector<vector<bool>>> dp(n + 1, vector<vector<bool>>(k + 1, vector<bool>(max_sum + 1, false)));
    dp[0][0][0] = true;

    for (int i = 1; i <= n; i++) {
        int val = a_shift[i - 1];
        for (int c = 0; c <= k; c++) {
            for (int s = 0; s <= max_sum; s++) {
                // กรณีไม่เลือกยูนิต i-1 เข้าฝ่ายที่ 1
                if (dp[i - 1][c][s]) {
                    dp[i][c][s] = true;
                }
                // กรณีเลือกยูนิต i-1 เข้าฝ่ายที่ 1
                if (c > 0 && s >= val && dp[i - 1][c - 1][s - val]) {
                    dp[i][c][s] = true;
                }
            }
        }
    }

    // 3. หาผลรวม s_best ของฝ่ายที่ 1 ที่ทำให้ผลต่างผลรวมสองฝ่ายน้อยที่สุด
    int best_s = -1;
    int min_diff = 1e9;

    for (int s = 0; s <= max_sum; s++) {
        if (dp[n][k][s]) {
            int orig_s1 = s - k * C;
            int orig_s2 = total_orig_sum - orig_s1;
            int diff = abs(orig_s1 - orig_s2);

            if (diff < min_diff) {
                min_diff = diff;
                best_s = s;
            }
        }
    }

    // 4. Backtrack เพื่อแยกยูนิตเข้าแต่ละฝ่าย
    vector<int> team1, team2;
    int curr_c = k;
    int curr_s = best_s;

    for (int i = n; i >= 1; i--) {
        int val = a_shift[i - 1];
        bool chosen_for_team1 = false;

        if (curr_c > 0 && curr_s >= val && dp[i - 1][curr_c - 1][curr_s - val]) {
            chosen_for_team1 = true;
        }

        if (chosen_for_team1) {
            team1.push_back(a[i - 1]);
            curr_c--;
            curr_s -= val;
        } else {
            team2.push_back(a[i - 1]);
        }
    }

    // กลับลำดับผลลัพธ์เพื่อให้ตรงตามลำดับข้อมูลนำเข้าเดิม
    reverse(team1.begin(), team1.end());
    reverse(team2.begin(), team2.end());

    // 5. แสดงผลลัพธ์
    for (int i = 0; i < (int)team1.size(); i++) {
        cout << team1[i] << (i == (int)team1.size() - 1 ? "" : " ");
    }
    cout << "\n";

    for (int i = 0; i < (int)team2.size(); i++) {
        cout << team2[i] << (i == (int)team2.size() - 1 ? "" : " ");
    }
    cout << "\n";

    return 0;
}