Submission

Score: 30

User: chokun

Problemset: ประลอง

Language: cpp

Time: 0.003 second

Submitted On: 2026-10-14 19:26:38

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

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

unordered_set<long long> visited;
vector<bool> in_team1;

bool dfs(int idx, int count, int curr_sum){
    if(count == target_k && curr_sum == best_sum){
        return true;
    }

    if(idx == n || count > target_k || (target_k - count) > (n - idx)){
        return false;
    }

    long long state = ((long long)idx << 45) | ((long long)count << 35) | (long long)(curr_sum + offset);
    if (visited.count(state)) {
        return false;
    }
    visited.insert(state);

    in_team1[idx] = true;
    if (dfs(idx + 1, count + 1, curr_sum + arr[idx])) {
        return true;
    }
    in_team1[idx] = false;

    if (dfs(idx + 1, count, curr_sum)) {
        return true;
    }

    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    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];
    }
    
    target_k = n / 2;
    offset = -min_possible;
    int S_range = max_possible - min_possible + 1;
    
    vector<vector<bool>> dp(target_k + 1, vector<bool>(S_range, false));
    dp[0][offset] = true;
    
    for (int i = 0; i < n; i++) {
        int x = arr[i];
        for (int j = target_k; j >= 1; j--) {
            for (int s = 0; s < S_range; s++) {
                if (dp[j-1][s]) {
                    int new_s = s + x;
                    if (new_s >= 0 && new_s < S_range) {
                        dp[j][new_s] = true;
                    }
                }
            }
        }
    }
    
    int best_diff = 2e9;
    best_sum = 0;
    for (int s = 0; s < S_range; s++) {
        if (dp[target_k][s]) {
            int actual_sum = s - offset;
            int diff = abs(2 * actual_sum - total_sum);
            if (diff < best_diff) {
                best_diff = diff;
                best_sum = actual_sum;
            }
        }
    }
    
    in_team1.assign(n, false);
    dfs(0, 0, 0);
    
    // แสดงผลลัพธ์ฝ่ายที่ 1
    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";
}