Submission

Score: 20

User: chokun

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2026-10-14 19:49:17

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

int n;
vector<int> arr;
int total_sum;
int min_diff = 2e9;
vector<int> best_team1_indices;

void find_teams(int idx, int count, int curr_sum, int target_k, vector<int>& current_indices) {
    if (count == target_k) {
        int diff = abs(2 * curr_sum - total_sum);
        if (diff < min_diff) {
            min_diff = diff;
            best_team1_indices = current_indices;
        }
        return;
    }
    
    if (idx == n || (target_k - count) > (n - idx)) {
        return;
    }
    
    current_indices.push_back(idx);
    find_teams(idx + 1, count + 1, curr_sum + arr[idx], target_k, current_indices);
    current_indices.pop_back();
    
    find_teams(idx + 1, count, curr_sum, target_k, current_indices);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> n)) return 0;
    
    arr.resize(n);
    total_sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        total_sum += arr[i];
    }
    
    int k1 = n / 2;
    int k2 = (n + 1) / 2;
    
    vector<int> current_indices;
    
    find_teams(0, 0, 0, k1, current_indices);
    
    if (k1 != k2) {
        find_teams(0, 0, 0, k2, current_indices);
    }
    
    vector<bool> in_team1(n, false);
    for (int index : best_team1_indices) {
        in_team1[index] = true;
    }
    
    bool first = true;
    for (int i = 0; i < n; i++) {
        if (in_team1[i]) {
            if (!first) cout << " ";
            cout << arr[i];
            first = false;
        }
    }
    cout << "\n";
    
    first = true;
    for (int i = 0; i < n; i++) {
        if (!in_team1[i]) {
            if (!first) cout << " ";
            cout << arr[i];
            first = false;
        }
    }
    cout << "\n";
}