Submission

Score: 60

User: NJTYTYTY

Problemset: ประลอง

Language: cpp

Time: 0.005 second

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    int total = 0;

    for (int &x : a) {
        cin >> x;
        total += x;
    }

    // จำนวนสมาชิกที่ฝ่าย 1 ต้องมี
    int k = n / 2;

    /*
        dp[cnt] = map จาก sum -> mask
        mask ใช้เก็บว่ามี index ไหนถูกเลือกเข้าฝ่าย 1
    */
    vector<unordered_map<int, unsigned long long>> dp(k + 1);

    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {

        // เดินย้อนจาก k ลงมา เพื่อไม่ให้ใช้สมาชิกตัวเดิมซ้ำ
        for (int cnt = min(k, i + 1); cnt >= 1; cnt--) {

            for (auto [sum, mask] : dp[cnt - 1]) {

                int newSum = sum + a[i];
                unsigned long long newMask =
                    mask | (1ULL << i);

                // เก็บ state นี้ถ้ายังไม่มี
                if (!dp[cnt].count(newSum)) {
                    dp[cnt][newSum] = newMask;
                }
            }
        }
    }

    // หาผลรวมของฝ่าย 1 ที่ทำให้ต่างจากฝ่าย 2 น้อยที่สุด
    int bestSum = 0;
    long long bestDiff = LLONG_MAX;
    unsigned long long bestMask = 0;

    for (auto [sum, mask] : dp[k]) {

        long long diff =
            llabs((long long)sum - (total - sum));

        if (diff < bestDiff) {
            bestDiff = diff;
            bestSum = sum;
            bestMask = mask;
        }
    }

    // แสดงฝ่าย 1
    bool first = true;

    for (int i = 0; i < n; i++) {
        if (bestMask & (1ULL << i)) {
            if (!first) cout << ' ';
            cout << a[i];
            first = false;
        }
    }

    cout << '\n';

    // แสดงฝ่าย 2
    first = true;

    for (int i = 0; i < n; i++) {
        if (!(bestMask & (1ULL << i))) {
            if (!first) cout << ' ';
            cout << a[i];
            first = false;
        }
    }

    cout << '\n';

    return 0;
}