Submission

Score: 70

User: mik

Problemset: ประลอง

Language: cpp

Time: 0.004 second

Submitted On: 2026-10-11 17:03:55

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <tuple>

using namespace std;

int n;
vector<int> arr;
int total_sum = 0;
int best_diff = INT_MAX;
vector<int> best_indices;
set<tuple<int, int, int>> memo;

void backtrack(int idx, int count, int current_sum, int target_k, vector<int>& current_indices) {
    if (count == target_k) {
        int diff = abs(total_sum - 2 * current_sum);
        if (diff < best_diff) {
            best_diff = diff;
            best_indices = current_indices;
        }
        return;
    }
    if (idx == n) return;
    if (count + (n - idx) < target_k) return;

    tuple<int, int, int> state = {idx, count, current_sum};
    if (memo.count(state)) return;

    current_indices.push_back(idx);
    backtrack(idx + 1, count + 1, current_sum + arr[idx], target_k, current_indices);
    current_indices.pop_back();

    backtrack(idx + 1, count, current_sum, target_k, current_indices);

    memo.insert(state);
}

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];
    }

    vector<int> targets;
    if (n % 2 == 0) {
        targets = {n / 2};
    } else {
        targets = {n / 2, n / 2 + 1};
    }

    for (int target_k : targets) {
        memo.clear();
        vector<int> current_indices;
        backtrack(0, 0, 0, target_k, current_indices);
    }

    vector<bool> chosen(n, false);
    for (int idx : best_indices) {
        chosen[idx] = true;
    }

    vector<int> team1, team2;
    for (int i = 0; i < n; ++i) {
        if (chosen[i]) {
            team1.push_back(arr[i]);
        } else {
            team2.push_back(arr[i]);
        }
    }
    for (size_t i = 0; i < team2.size(); ++i) {
        cout << team2[i] << (i == team2.size() - 1 ? "" : " ");
    }

    cout << "\n";
    for (size_t i = 0; i < team1.size(); ++i) {
        cout << team1[i] << (i == team1.size() - 1 ? "" : " ");
    }

    cout << "\n";

    return 0;
}