Submission

Score: 30

User: chokun

Problemset: ประลอง

Language: cpp

Time: 0.005 second

Submitted On: 2026-10-14 19:57:21

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

int n;
vector<int> arr;
int total_sum;
int target_k;
int best_sum;
int offset;

vector<vector<vector<bool>>> dp_table;
vector<bool> in_team1;
bool found_path = false;

void back_track_path(int idx, int count, int curr_sum) {
    if (found_path) return;
    
    if (count == target_k) {
        if (curr_sum == best_sum) {
            found_path = true;
        }
        return;
    }
    
    if (idx == n || (target_k - count) > (n - idx)) {
        return;
    }
    
    int s_idx = curr_sum + offset;
    
    int next_s_take = curr_sum + arr[idx] + offset;
    if (count + 1 <= target_k && next_s_take >= 0 && next_s_take < dp_table[0][0].size()) {
        if (dp_table[idx + 1][count + 1][next_s_take]) {
            in_team1[idx] = true;
            back_track_path(idx + 1, count + 1, curr_sum + arr[idx]);
            if (found_path) return;
            in_team1[idx] = false;
        }
    }
    
    if (dp_table[idx + 1][count][s_idx]) {
        in_team1[idx] = false;
        back_track_path(idx + 1, count, curr_sum);
        if (found_path) return;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> n)) return 0;
    
    arr.resize(n);
    int min_possible = 0;
    int max_possible = 0;
    total_sum = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        total_sum += arr[i];
        if (arr[i] < 0) min_possible += arr[i];
        else max_possible += arr[i];
    }
    
    int k1 = n / 2;
    int k2 = (n + 1) / 2;
    int max_k = k2;
    
    offset = -min_possible;
    int S_range = max_possible - min_possible + 1;
    
    dp_table.assign(n + 1, vector<vector<bool>>(max_k + 1, vector<bool>(S_range, false)));
    dp_table[0][0][offset] = true;
    
    for (int i = 0; i < n; i++) {
        int x = arr[i];
        for (int j = 0; j <= max_k; j++) {
            for (int s = 0; s < S_range; s++) {
                if (dp_table[i][j][s]) {
                    dp_table[i + 1][j][s] = true;
                    if (j + 1 <= max_k && s + x >= 0 && s + x < S_range) {
                        dp_table[i + 1][j + 1][s + x] = true;
                    }
                }
            }
        }
    }
    
    int best_diff = 2e9;
    target_k = k1;
    best_sum = 0;
    
    vector<int> candidates = {k1};
    if (k1 != k2) candidates.push_back(k2);
    
    for (int tk : candidates) {
        for (int s = 0; s < S_range; s++) {
            if (dp_table[n][tk][s]) {
                int actual_sum = s - offset;
                int diff = abs(2 * actual_sum - total_sum);
                if (diff < best_diff) {
                    best_diff = diff;
                    target_k = tk;
                    best_sum = actual_sum;
                }
            }
        }
    }
    
    in_team1.assign(n, false);
    found_path = false;
    back_track_path(0, 0, 0);
    
    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";
}