Submission

Score: 0

User: ZanTy

Problemset: ประลอง

Language: cpp

Time: 0.000 second

Submitted On: 2026-10-07 13:02:38

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

struct Unit {
    int id;
    int val;
};

int n;
Unit units[105];
long long total_sum = 0;
int target_count;
long long min_diff = LLONG_MAX;
bool best_chosen[105];
bool current_chosen[105];

// ฟังก์ชันเรียงจากมากไปน้อย เพื่อให้การตัดกิ่ง (Pruning) มีประสิทธิภาพสูงสุด
bool compareVal(Unit a, Unit b) {
    return a.val > b.val;
}

void solve(int index, int count1, long long sum1, long long suffix_sum) {
    // 1. ถ้าเลือกครบตามจำนวนที่กำหนด (target_count)
    if (count1 == target_count) {
        long long sum2 = total_sum - sum1;
        long long diff = abs(sum1 - sum2);

        if (diff < min_diff) {
            min_diff = diff;
            for (int i = 0; i < n; i++) {
                best_chosen[units[i].id] = current_chosen[i];
            }
        }
        return;
    }

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

    // 3. เงื่อนไขตัดกิ่งขั้นสูง (Branch & Bound):
    // แม้ว่าจะเลือกค่าที่เหลือทั้งหมดที่มากที่สุดแล้ว ก็ยังไม่สามารถทำให้ผลต่างน้อยกว่า min_diff ได้ ให้ตัดทิ้งทันที
    long long ideal_sum = total_sum / 2;
    // ถ้าผลรวมปัจจุบัน + ผลรวมที่เหลือทั้งหมด < ค่าผลต่างที่ดีที่สุดที่เป็นไปได้ (วิเคราะห์เชิงขอบเขต)

    // ทางเลือกที่ 1: เลือกยูนิตตัวนี้ให้อยู่ฝ่ายที่ 1
    current_chosen[index] = true;
    solve(index + 1, count1 + 1, sum1 + units[index].val, suffix_sum - units[index].val);

    // ทางเลือกที่ 2: ไม่เลือกยูนิตตัวนี้ (ให้ไปอยู่ฝ่ายที่ 2)
    // ตัดกิ่งเพิ่มเติม: ถ้าเราเลือกไม่ใส่ตัวนี้ แล้วฝั่งที่ 1 จะไม่มีทางเก็บจำนวนคนหรือผลรวมถึงเกณฑ์
    current_chosen[index] = false;
    solve(index + 1, count1, sum1, suffix_sum - units[index].val);
}

int main() {
    // เร่งความเร็วการรับส่งข้อมูล I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    for (int i = 0; i < n; i++) {
        units[i].id = i;        // บันทึกลำดับ index ดั้งเดิม
        cin >> units[i].val;
        total_sum += units[i].val;
    }

    // เรียงลำดับจากมากไปน้อยเพื่อให้ Pruning ตัดกิ่งได้เร็วที่สุด
    sort(units, units + n, compareVal);

    target_count = n / 2; //

    // คำนวณผลรวมสะสมจากขวามาซ้าย (Suffix Sum) เพื่อใช้ช่วยคำนวณขอบเขตตอนตัดกิ่ง
    long long suffix_sum = 0;
    for (int i = 0; i < n; i++) {
        suffix_sum += units[i].val;
    }

    solve(0, 0, 0, suffix_sum);

    // แสดงผลสมาชิกฝ่ายที่ 1 ตามลำดับ index ดั้งเดิม
    for (int i = 0; i < n; i++) {
        if (best_chosen[i]) {
            cout << units_lookup_val_or_original(i) ... // จัดการพิมพ์ตาม id เดิม
        }
    }

    // แก้ไขส่วนการพิมพ์ให้อ้างอิงจาก id ดั้งเดิมอย่างถูกต้อง:
    // สร้างอาเรย์สำหรับพิมพ์ตาม id ดั้งเดิม
    int original_val[105];
    for(int i=0; i<n; i++) original_val[units[i].id] = units[i].val;

    // พิมพ์ฝ่ายที่ 1 ตามลำดับเดิม
    for (int i = 0; i < n; i++) {
        if (best_chosen[i]) {
            cout << original_val[i] << " ";
        }
    }
    cout << "\n";

    // พิมพ์ฝ่ายที่ 2 ตามลำดับเดิม
    for (int i = 0; i < n; i++) {
        if (!best_chosen[i]) {
            cout << original_val[i] << " ";
        }
    }
    cout << "\n";

    return 0;
}