Submission

Score: 100

User: chokun

Problemset: ประลอง

Language: cpp

Time: 0.004 second

Submitted On: 2026-10-14 20:16:26

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<int> arr(n);
    int min_possible = 0;
    int max_possible = 0;
    int 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 target_k = n / 2;
    
    int offset = -min_possible; 
    int S_range = max_possible - min_possible + 1;
    
    int dim2 = target_k + 1;
    int dim3 = S_range;
    
    long long total_size = (long long)(n + 1) * dim2 * dim3;
    vector<bool> dp(total_size, false);
    
    auto get_idx = [&](int i, int j, int s) {
        return (long long)i * dim2 * dim3 + (long long)j * dim3 + s;
    };
    
    dp[get_idx(n, 0, offset)] = true;
    
    for (int i = n - 1; i >= 0; i--) {
        int x = arr[i];
        for (int j = 0; j <= target_k; j++) {
            for (int s = 0; s < S_range; s++) {
                if (dp[get_idx(i + 1, j, s)]) {
                    dp[get_idx(i, j, s)] = true;
                }
                if (j > 0 && s - x >= 0 && s - x < S_range && dp[get_idx(i + 1, j - 1, s - x)]) {
                    dp[get_idx(i, j, s)] = true;
                }
            }
        }
    }
    
    int best_diff = 2e9;
    vector<int> valid_sums;
    
    for (int s = 0; s < S_range; s++) {
        if (dp[get_idx(0, target_k, s)]) {
            int actual_sum = s - offset;
            int diff = abs(2 * actual_sum - total_sum);
            
            if (diff < best_diff) {
                best_diff = diff;
                valid_sums.clear();
                valid_sums.push_back(s);
            } else if (diff == best_diff) {
                valid_sums.push_back(s);
            }
        }
    }
    
    vector<int> best_path;
    bool has_best_path = false;
    
    for (int b_s : valid_sums) {
        int rem_j = target_k;
        int rem_s = b_s;
        vector<int> path;
        path.reserve(n);
        
        for (int i = 0; i < n; i++) {
            if (dp[get_idx(i + 1, rem_j, rem_s)]) {
                path.push_back(0); 
            } else {
                int x = arr[i];
                path.push_back(1); 
                rem_j--;
                rem_s -= x;
            }
        }
        
        if (!has_best_path || path < best_path) {
            best_path = path;
            has_best_path = true;
        }
    }
    
    bool first = true;
    for (int i = 0; i < n; i++) {
        if (best_path[i] == 1) {
            if (!first) cout << " ";
            cout << arr[i];
            first = false;
        }
    }
    cout << "\n";
    
    first = true;
    for (int i = 0; i < n; i++) {
        if (best_path[i] == 0) {
            if (!first) cout << " ";
            cout << arr[i];
            first = false;
        }
    }
    cout << "\n";
}