Submission

Score: 20

User: ZanTy

Problemset: ประลอง

Language: cpp

Time: 0.004 second

Submitted On: 2026-10-07 12:57:56

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

int n;
int arr[105];
long long total_sum = 0;
int target_count;
long long min_diff = LLONG_MAX;
int best_mask = 0;

// ฟังก์ชัน Backtracking พร้อมเช็คเงื่อนไข
void solve(int index, int count1, long long sum1, int current_mask) {
    // ถ้าเลือกครบตามจำนวนที่ต้องการ
    if (count1 == target_count) {
        long long sum2 = total_sum - sum1;
        long long diff = abs(sum1 - sum2);

        if (diff < min_diff) {
            min_diff = diff;
            best_mask = current_mask;
        }
        return;
    }

    // Pruning: ถ้าเลือกจนหมดแล้วแต่ยังไม่ครบจำนวน หรือตัวที่เหลือไม่พอให้เลือก
    if (index >= n || (count1 + (n - index)) < target_count) {
        return;
    }

    // ทางเลือกที่ 1: เลือกตัวปัจจุบันเข้าฝ่ายที่ 1
    solve(index + 1, count1 + 1, sum1 + arr[index], current_mask | (1 << index));

    // ทางเลือกที่ 2: ไม่เลือกตัวปัจจุบัน (ให้ไปอยู่ฝ่ายที่ 2)
    solve(index + 1, count1, sum1, current_mask);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        total_sum += arr[i];
    }

    target_count = n / 2; //[cite: 1]

    solve(0, 0, 0, 0);

    // แสดงผลสมาชิกฝ่ายที่ 1[cite: 1]
    for (int i = 0; i < n; i++) {
        if ((best_mask & (1 << i)) != 0) {
            cout << arr[i] << " ";
        }
    }
    cout << "\n";

    // แสดงผลสมาชิกฝ่ายที่ 2[cite: 1]
    for (int i = 0; i < n; i++) {
        if ((best_mask & (1 << i)) == 0) {
            cout << arr[i] << " ";
        }
    }
    cout << "\n";

    return 0;
}