Submission

Score: 0

User: NJTYTYTY

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2026-08-11 19:51:22

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

using namespace std;

// กำหนด MAX_SUM ให้ครอบคลุมผลรวมสูงสุดที่เป็นไปได้
const int MAX_SUM = 200000; 

// dp[i][c] เก็บ bitset ผลรวมที่เป็นไปได้เมื่อพิจารณาถึงยูนิตที่ i และเลือกมา c ตัว
// ประกาศเป็น Global Array เพื่อป้องกัน Stack Overflow และใช้ความเร็วสูงสุด
bitset<MAX_SUM + 1> dp[101][51];

int main() {
    // เพิ่มความเร็วการอ่าน/เขียนข้อมูล
    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 sum_shift = 0;
    for (int i = 0; i < n; i++) {
        a_shift[i] = a[i] + C;
        sum_shift += a_shift[i];
    }

    int k = n / 2;

    // Base case: 0 ยูนิต ผลรวมเป็น 0
    dp[0][0][0] = 1;

    // 2. Dynamic Programming ด้วย Bitwise Operations
    for (int i = 1; i <= n; i++) {
        int val = a_shift[i - 1];
        for (int c = 0; c <= k; c++) {
            // ไม่เลือกยูนิตที่ i-1
            dp[i][c] = dp[i - 1][c];
            // เลือกยูนิตที่ i-1 (ขยับบิตไปทางซ้ายเท่ากับขนาด val)
            if (c > 0) {
                dp[i][c] |= (dp[i - 1][c - 1] << val);
            }
        }
    }

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

    for (int s = 0; s <= sum_shift; 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;
}