Submission

Score: 30

User: amongus

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-02 00:05:16

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second
#define ll long long
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

int n;
vector<int> a;
ll total_sum = 0;

ll min_diff = -1;
vector<bool> best_partition;
vector<bool> current_partition;

// Recursively explores all possible partitions
void find_partition(int k, ll current_team1_sum, int team1_size) {
    if (k == n) {
        // Base case: all units have been assigned
        int team2_size = n - team1_size;

        // Check if the team sizes are valid for the given n
        bool is_valid_size = false;
        if (n % 2 == 0) {
            if (team1_size == n / 2) is_valid_size = true;
        } else {
            if (team1_size == n / 2 || team1_size == (n + 1) / 2) is_valid_size = true;
        }

        if (is_valid_size) {
            ll team2_sum = total_sum - current_team1_sum;
            ll diff = abs(current_team1_sum - team2_sum);

            if (min_diff == -1 || diff < min_diff) {
                min_diff = diff;
                best_partition = current_partition;
            }
        }
        return;
    }

    // Choice 1: Place unit k in Team 1
    current_partition[k] = true;
    find_partition(k + 1, current_team1_sum + a[k], team1_size + 1);

    // Choice 2: Place unit k in Team 2
    current_partition[k] = false;
    find_partition(k + 1, current_team1_sum, team1_size);
}

void solve() {
    cin >> n;
    a.resize(n);
    current_partition.resize(n);
    total_sum = 0;
    min_diff = -1;

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

    find_partition(0, 0, 0);

    vector<int> team1, team2;
    for (int i = 0; i < n; ++i) {
        if (best_partition[i]) {
            team1.push_back(a[i]);
        } else {
            team2.push_back(a[i]);
        }
    }

    // The example output for n=11 prints the 5-person team first.
    // This ensures our output matches that convention.
    if (sz(team1) > sz(team2)) {
        swap(team1, team2);
    }
    
    for (int i = 0; i < sz(team1); ++i) {
        cout << team1[i] << (i == sz(team1) - 1 ? "" : " ");
    }
    cout << "\n";
    for (int i = 0; i < sz(team2); ++i) {
        cout << team2[i] << (i == sz(team2) - 1 ? "" : " ");
    }
    cout << "\n";
}

int main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    solve();
    return 0;
}